AOJ 0118 深度优先搜索DFS

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAX_H = 100;
 5 const int MAX_W = 100;
 6 
 7 //输入
 8 int H, W;
 9 char g[MAX_H][MAX_W + 1];
10 
11 int d[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};        //方向
12 
13 //深度优先遍历g[i][j]同类局域
14 void dfs(int x, int y, int c){
15     for(int i = 0; i < 4; i ++){
16         int nx = x + d[i][0], ny = y + d[i][1];
17         if(0 <= nx && nx < H && 0 <= ny && ny < W && g[nx][ny] == c){
18             g[nx][ny] = ‘1‘;
19             dfs(nx, ny, c);
20         }
21     }
22 }
23 
24 void solve(){
25     //遍历果园，每到一个新位置，遍历该位置能到达的地方
26     int ans = 0;
27     for(int i = 0; i < H; i ++){
28         for(int j = 0; j < W; j ++){
29             if(g[i][j] != ‘1‘){
30                 ans ++;
31                 char c = g[i][j];
32                 g[i][j] = ‘1‘;
33                 dfs(i, j, c);
34             }
35         }
36     }
37     printf("%d\n", ans);
38 }
39 
40 int main(int argc, char const *argv[]){
41 
42     while(scanf("%d %d", &H, &W)){
43         if(H == 0 && W == 0) break;
44         for(int i = 0; i < H; i ++){
45             scanf("%s", g[i]);
46         }
47         solve();
48     }
49 
50     return 0;
51 }