POJ NO.2386 Lake Counting(算水窪)

NO IMAGE

問題描述:

給你一個row*col的矩陣表示一塊田地,上面的’W’代表積水,’.’表示乾地,問這塊田地裡面的積水能匯聚成幾片水窪。

題目連結:點選開啟連結

思路:

從任意的‘W’開始,不停地把鄰接的部分用‘.’代替。1次DFS後與初始的這個W連線的所有W就都被替換成了‘.’,因此知道途中不再存在W為止,總共進行的DFS次數就是答案。—-《挑戰程式設計》

程式碼:

#include<cstdio>
#include<iostream>
using namespace std;
const int MAX = 10086;
int n, m;
char arr[MAX][MAX];
void dfs(int x, int y);
void solve();
int main()
{
while(~scanf("%d%d", &n, &m)){
for(int i = 0; i < n; i  )
scanf("%s", arr[i]);//注意輸入陣列的方式!!!%c會吞掉空格,但是%s不會!!!
solve();
}
return 0;
}
void dfs(int x, int y)
{
arr[x][y] = '.';
for(int xx = -1; xx <= 1; xx  )
for(int yy = -1; yy <= 1; yy  ){
int nx = x   xx, ny = y   yy;
if(0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny] == 'W') dfs(nx, ny);
}
return ;
}
void solve()
{
int cou = 0;
//注意這一步,被害慘了!!!
for(int i = 0; i < n; i  )
for(int j = 0; j < m; j  ){
if(arr[i][j] == 'W'){
dfs(i, j);
cou  ;
}
}
cout<< cou <<endl;
}