AOJ 0118 深度优先搜索

日文题。。。

题意：一个面积为H*W的果园，种了苹果，梨和蜜柑。相邻（上下左右）的果树属于同一个区域，问果园共有多少个区域。

分析：迷宫问题。对于每一个格子，可以用深度优先搜索把相同果树的格子遍历并标记。也就是说，每做一次DFS，消灭掉一个区域。只需要遍历果园，对每一个未被标记的格子做DFS，做DFS的次数就是果园的区域数。这里不需要另外用其他数组标记格子已访问，只需要将格子的元素改为一个不会出现的元素如1即可。

C++代码：

#include <cstdio>
#include <cstring>

const int MAX_H = 100;
const int MAX_W = 100;

//输入
int H, W;
char g[MAX_H][MAX_W + 1];

int d[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};        //方向

//深度优先遍历g[i][j]同类局域
void dfs(int x, int y, int c){
    for(int i = 0; i < 4; i ++){
        int nx = x + d[i][0], ny = y + d[i][1];
        if(0 <= nx && nx < H && 0 <= ny && ny < W && g[nx][ny] == c){
            g[nx][ny] = '1';
            dfs(nx, ny, c);
        }
    }
}

void solve(){
    //遍历果园，每到一个新位置，遍历该位置能到达的地方
    int ans = 0;
    for(int i = 0; i < H; i ++){
        for(int j = 0; j < W; j ++){
            if(g[i][j] != '1'){
                ans ++;
                char c = g[i][j];
                g[i][j] = '1';
                dfs(i, j, c);
            }
        }
    }
    printf("%d
", ans);
}

int main(int argc, char const *argv[]){

    while(scanf("%d %d", &H, &W)){
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i ++){
            scanf("%s", g[i]);
        }
        solve();
    }

    return 0;
}