UVA 572 Oil Deposits (DFS)

题目链接：http://acm.hust.edu.cn/vjudge/problem/19435

题意：

　　给你一个M 行N 列的矩阵，其中仅有两种符号，“@” 和 “×”，问你有多少个连通块，所谓连通就是一个“@” 的上下左右以及对角线有另外一个“@”，则说明者两个“@”连通的。

****@

*@@*@

*@**@

@@@*@

@@**@

比如此矩阵中仅有2个连通块。

思路：

　　从第一个“@”开始DFS ，找到与它连通的并标记为同一数字，直到所有连通的都标记完，再从下一个没被标记的“@”处DFS，并标记为另外一个数字，最后查看有多少个数字就可以了。

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #include <string>
 8 
 9 typedef long long LL;
10 using namespace std;
11 const double PI = acos(-1);
12 const int MAXN = 100;
13 int idx[MAXN + 3][MAXN + 3];
14 char map[MAXN + 3][MAXN + 3];
15 
16 void dfs(int x, int y, int cnt){
17     idx[x][y] = cnt;//都标记为同一数字
18     for(int i = -1; i <= 1; i++){//两层循环排查周围的点
19         for(int j = -1; j <= 1; j++){
20             if(x + i >= 0 && y + j >= 0 && idx[x + i][y + j] == 0 && map[x + i][y + j] == '@')//排除掉不满足情况的点
21                 dfs(x + i, y + j, cnt);
22         }
23     }
24 }
25 
26 int main(){
27     //freopen("input", "r", stdin);
28     int n, m;
29     while(scanf("%d%d", &n, &m) && (n != 0)){
30         memset(map, 0, sizeof(map));
31         memset(idx, 0, sizeof(idx));
32         for(int i = 0;  i < n; i++) scanf("%s", map[i]);
33         int cnt = 0;
34         for(int i = 0; i < n; i++){
35             for(int j = 0; j < m; j++){
36                 if(!idx[i][j] && map[i][j] == '@'){//每次都从没被标记且时“@”处开始新的DFS 
37                     dfs(i, j, ++cnt);
38                 }
39             }
40         }
41         printf("%d
", cnt);
42     }
43     return 0;
44 }