问题描述：
水洼数目有一个大小为N * M的院子，雨后积起了水，
八连通的积水被认为是连在一起的，请求出园子里面总共有多少水洼
限制条件
N, M <=100
测试集在代码后面
总体思路：
- 一个水洼一定是一个或多个W连接在一起的，所以可以先找到第一个W，然后看与这个W相连接的其他W，当他的周围没有W只有.的时候，就检查完了一个水洼
- 由于检查过的积水不能第二次被计算，所以一个巧妙的方法就是检查之后把他变成点（路过之处寸草不生）
#include<iostream> #include<string> #include<algorithm> using namespace std; // 剪枝：递归之前做限定 const int maxn = 20; int n, m, cnt = 0; char a[maxn][maxn]; void dfs(int i, int j){ a[i][j] = '.'; for(int k = -1; k < 2; k++){ //-1,0,1分别代表横坐标向左，不动，向右 for(int l = -1; l < 2; l++){ //纵坐标 if(k == 0 && l == 0) continue;//扣去x和y都不动的情况 if(i+k <= n-1 && i+k >= 0 && j+l <= m-1 && j+l >= 0){//检查x和y动了之后是否越界 if(a[i+k][j+l] == 'W'){//如果是一个水洼，继续深搜 dfs(i+k, j+l); } } } } } int main(){ cin >> n >> m; for(int i = 0; i < n; i++){ string s; cin >> s; for(int j = 0; j < m; j++){ a[i][j] = s[j]; } } for(int i = 0; i< n; i++){ for(int j = 0; j < m; j++){ if(a[i][j] == 'W'){ dfs(i,j); cnt++; } } } cout << cnt << endl; return 0; } /* 测试集： ..W.....WW .W......W. WW.....WW. ........W. ....WW..WW ....W...W. ...W.W.... ..W...W... ...W.W.... ....W..... 答案： 3 */
