试题描述

有一个大小为M*N的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里共有多少水洼？（八连通指的是下面图中相对W的*的部分）

***

*W*

***

限制条件：

N,M≤100

输入

第一行包含两个正整数 N 和 M，表示将一个园子地面分成N*M块方格，N 行，M列，接下来的 N 行描述了园子地面状况，其中‘W’表示积水的水洼，‘.’表示没有积水。

输出

仅一个数，表示水洼的总数。

输入示例

10 12

w........ww.

.www.....www

....ww...ww.

.........ww.

.........w..

..w......w..

.w.w.....ww.

w.w.w.....w.

.w.w......w.

..w.......w.

输出示例

3

其实就是八连块。用dfs（即深度搜索）可以解决。

1 #include 
      
        2 #define MAXN 101 3 using namespace std; 4 char a[MAXN][MAXN]; 5 int m,n,flag[MAXN][MAXN]; 6  7 void dfs(int i,int j,int id)  //dfs函数每运行一次，答案（即cnt）++；  8 { 9     if(i<0||i>=m||j<0||j>=n) return;  //如果出界，退出递归 10     if(flag[i][j]>0||a[i][j]!='w') return;  //如果当前格子搜索过或者不是水洼，退出递归 11     flag [i][j]=id;//记录当前格子被访问过 12     dfs(i-1,j-1,id); //开始八连块 13     dfs(i-1,j,id);14     dfs(i-1,j+1,id);15     dfs(i,j-1,id);16     dfs(i,j+1,id);17     dfs(i+1,j-1,id);18     dfs(i+1,j,id);19     dfs(i+1,j+1,id);20 }21 int main()22 {23     int j,i,cnt=0;24     cin>>m>>n;25     for(i=0;i
       
        >a[i][j];27     for(i=0;i