用dfs求聯通塊（UVa572）

一、題目

輸入一個m行n列的字元矩陣，統計字元“@”組成多少個八連塊。如果兩個字元所在的格子相鄰（橫、豎、或者對角線方向），就說它們屬于同一個八連塊。

二、解題思路

和前面的二叉樹周遊類似，圖也有DFS和BFS周遊。由于DFS更容易編寫，一般用DFS找聯通塊：從每個“@”格子出發，遞歸周遊與之相鄰的“@”格子，标記相同的“聯通分量标号”。這樣在通路之前需檢查它是否已經有了編号，進而避免一個格子通路多次。

三、代碼實作

1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 const int maxn = 100 + 10;
 6 char field[maxn][maxn];
 7 int N, M;
 8 
 9 void dfs(int x, int y)
10 {
11     field[x][y] = '*';                      //這裡通過把“@”換成“*”，進而避免重複
12     for (int dx = -1; dx <= 1; dx++)
13         for (int dy = -1; dy <= 1; dy++)
14         {
15             int nx = x + dx; int ny = y + dy;
16             if (nx >= 0 && nx < N && ny >= 0 && ny < M && field[nx][ny] == '@')
17                 dfs(nx, ny);
18         }
19     return;
20 }
21 void slove()
22 {
23     int res = 0;
24     for (int i = 0; i < N; i++)
25         for (int j = 0; j < M; j++)
26         {
27             if (field[i][j] == '@')
28             {
29                 dfs(i, j);
30                 res++;          //周遊完一個連通分量，答案加一
31             }
32         }
33     printf("%d\n", res);
34 }
35 int main()
36 {
37     while (scanf("%d%d", &N, &M) == 2 && N)
38     {
39         for (int i = 0; i < N; i++)
40             for (int j = 0; j < M; j++)
41                 cin >> field[i][j];
42 
43         slove();
44     }
45     return 0;
46 }      

個性簽名：時間會解決一切