題目大意：有一個(gè)大小為N*M的園子，雨后積起了水。八連通的積水被認(rèn)為是連接在一起的。請(qǐng)求出園子里總共有多少水洼？
（八連通指下圖中相當(dāng)于W的*）
***
*W*
***
題目分析；從任意的W開始，不同的用一個(gè)vis數(shù)組標(biāo)記是否訪問過。一次DFS后與初始的這個(gè)W相連的W就都被標(biāo)記過了。因此知道途中不再存在W為止，總共進(jìn)行DFS的次數(shù)就是答案了。
#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 閱讀(551)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告