题目大意：有一个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？
（八连通指下图中相当于W的*）
***
*W*
***
题目分析；从任意的W开始，不同的用一个vis数组标记是否访问过。一次DFS后与初始的这个W相连的W就都被标记过了。因此知道途中不再存在W为止，总共进行DFS的次数就是答案了。
#include <cstdio>
#include <cstring>
const int maxn = 101;
int n, m, ans;
char g[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int x, int y) {
if(vis[x][y] == true || g[x][y] != 'W') return;
vis[x][y] = true;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++) {
if(!i && !j || x + i < 0 || x + i >= n || y + j < 0 || y + j >= m) continue;
dfs(x+i, y+j);
}
return;
}
int main() {
while(~scanf("%d%d" , &n, &m)) {
for(int i=0;i<n;i++) {
scanf("%s", g[i]);
memset(vis+i, false, sizeof(bool)*(m));
}
ans = 0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j] == 'W' && !vis[i][j]) {
ans ++;
dfs(i, j);
}
printf("%d\n", ans);
}
return 0;
}
posted on 2015-02-11 15:29
JulyRina 阅读(531)
评论(0) 编辑 收藏 引用 所属分类:
解题报告