当前位置: 首页 > 编程语言 > 算法 > 正文

水洼的数量算法 代码(C)

时间:2015-10-28

题目: 有一个大小为N*M的园子, 雨后起了积水. 八连通的积水被认为是连接在一起的. 请求出园子里总共有多少水洼.

使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止.

则所有的深度优先搜索的次数, 就是水洼数. 时间复杂度O(8*M*N)=O(M*N).

代码:

/* 
 * main.cpp 
 * 
 *  Created on: 2014.7.12 
 *本栏目更多精彩内容:http://www.bianceng.cn/Programming/sjjg/
 *      Author: spike 
 */
      
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
      
class Program {  
    static const int MAX_N=20, MAX_M=20;  
    int N = 10, M = 12;  
    char field[MAX_N][MAX_M+1] = {  
            "W........WW.",  
            ".WWW.....WWW",  
            "....WW...WW.",  
            ".........WW.",  
            ".........W..",  
            "..W......W..",  
            ".W.W.....WW.",  
            "W.W.W.....W.",  
            ".W.W......W.",  
            "..W.......W."};  
    void dfs(int x, int y) {  
        field[x][y] = '.';  
        for (int dx = -1; dx <= 1; dx++) {  
            for (int dy = -1; dy <= 1; dy++) {  
                int nx = x+dx, ny = y+dy;  
                if (0<=dx&&nx<N&&0<=ny&&ny<=M&&field[nx][ny]=='W') dfs(nx, ny);  
            }  
        }  
        return;  
    }  
public:  
    void solve() {  
        int res=0;  
        for (int i=0; i<N; i++) {  
            for (int j=0; j<M; j++) {  
                if (field[i][j] == 'W') {  
                    dfs(i,j);  
                    res++;  
                }  
            }  
        }  
        printf("result = %d\n", res);  
    }  
};  
      
      
int main(void)  
{  
    Program P;  
    P.solve();  
    return 0;  
}

输出:

result = 3

作者:csdn博客 Mystra