问题描述
有一个大小为N×MN×M N\times MN×M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？八连通指的是下图中相对W的∗部分，‘W’表示积水，’ * '表示没有积水。
∗∗∗ ∗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*
输出样例
问题分析
假如这个红色的地方有水,首先以它为中心，进行找,找到了就以新的为中心继续往下找
但这样会出现一个问题，就是它会往回走,这样就会陷入死循环，怎么样才能避免这样的事情发生囊？大家先思考下,这里留个悬念下面讲
继续往前走，发现前面没有积水了，它开始找另外方向有没有积水，发现没有后,就会退到上一层，继续寻找其他方向有没有积水，没有继续往回退，直到退到第一个积水的八个方向都走完,这样就完成了。
ok，我们开始思考怎么样才能避免它往回走陷入死循环的情况囊?
只要我们走到的位置有积水,走过后我们就把积水抽掉，让它变的干燥，就是上面例子中给的当走到的地方有积水也就是'W‘走过后把它变成'*’,这样遍历完后他都变成‘*'了也就结束了，避免了死循环.
这道题很经典，这种思想可以说在深搜中屡试不爽,所以我们可以把这个当做例题模板，背下来,遇到类似的题，像迷宫,岛屿之类的可以直接套模板。
话不多说,
放码过来
#include<iostream> #include<cstring> using namespace std; int cnts; //n是行，m是列 int n, m; void dfs(string* a, int i, int j) { //a[i][j] = '.'; //if (i > 0 && a[i - 1][j] == 'W')dfs(a, i - 1, j);//上方 //if (i <n-1&& a[i + 1][j] == 'W')dfs(a, i + 1, j);//下方 //if (j > 0 && a[i][j - 1] == 'W')dfs(a, i, j - 1);//左 //if (j < m - 1 && a[i][j + 1] == 'W')dfs(a, i, j + 1);//右 //..... a[i][j] = '.'; for (int k = -1; k < 2; k++)//-1,0，1 { for (int l = -1; l < 2; l++)//-1,0,1 { if (k == 0 && l == 0)continue; if (i + k >= 0 && i + k <= n - 1 && j + l >= 0 && j + 1 <= m - 1) { if (a[i + k][j + l] == 'W') { dfs(a, i + k, j + l); } } } } } int main() { cin >> n >> m; string* a=new string[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'W') { dfs(a,i,j); cnts++; } } } cout << cnts << endl; return 0; }
我们再回来看下这个题目:
我们使用双重for循环,来遍历这个二维数组,首先发现第一组的'W’就DFS遍历,遇到'W‘就继续往下走,直到把第一组的所有'W’都变为'.',就返回,这时第一个水洼就遍历完了,cnts对应加1,继续进行for循环找下一组'W‘的位置,如上图的2和3.重复1的操作,直到把所有的'W’遍历为'.‘这样for循环也就结束了.cnts此时的数就是水洼数。
这里我们思考一个问题,这里可以回溯嘛？答案肯定是不可以的，因为当我们遍历并把其改为'.’再进行回溯又变成了'W‘这样来来回回根本统计不完,所以回溯的使用要根据每个题目的不同进行灵活判断。
