dfs模板例：[洛谷]P1506 拯救oibh总部

题目详情

思路

我们以下图为例子分析：

4 5
00000
00*00
0*0*0
00*00

我们可以采用解决连通块的思想，将可联通的0块全部标记为*，最终再计数矩阵中的0的数目就是没有被淹没的总部数量。

也即搜索后的结果为：

4 5
*****
*****
**0**
*****

计数最终的总部为1个。

如何搜索是关键，那么我们使用dfs，如下搜索：

#include<bits/stdc++.h>
using namespace std;
int m, n;
int s = 0;
char ch[501][501];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void dfs(int x,int y) {
	if (x<1 || y<1 || x>m || y>n || ch[x][y] == '*')return;//搜索到边界就退出
	ch[x][y] = '*';//dfs中进行的操作步骤
	/*dfs中的步进递归步骤*/
	for (int i = 0; i < 4; i++) {
		int newx = x + dx[i];
		int newy = y + dy[i];
		dfs(newx, newy);
	}

}
int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ch[i][j];
		}
	}
	dfs(1, 1);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if(ch[i][j]=='0')
				s++;
		}
	}
	cout << s;
}

好的，此时我们丢进去测试一下：

好好好好好好，一顿操作猛如虎，一看测试全没过，这是为什么呢？

我们不妨看看代码中的测试逻辑：

当遇到这种案例时候：

5 5
0*000
*0000
00000
00000
00000

我们易得结果应该是0，丢进去测试下结果为22？

这是因为当dfs(1,1）开始时候，（1，1）修改为*，然后就因为四周都为边界而弹出，不再进行dfs了，要想再实现计算，那就只能再在（1，3）处手动执行一遍dfs(1，3)。

这只是具体针对这道题来说，那么如何一劳永逸的解决问题呢？

通过上面的分析我们可以知道，出现问题的原因是因为在搜索时候dfs陷入了死胡同而不能继续进行，我们可以考虑打破”墙壁“，将dfs从边界开始进行（相当于在矩阵外再围一圈），这样就能避免dfs陷入死胡同，修改代码如下：

#include<bits/stdc++.h>
using namespace std;
int m, n;
int s = 0;
char ch[501][501];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void dfs(int x,int y) {
	if (x<0 || y<0 || x>m+1 || y>n+1 || ch[x][y] == '*')return;//多搜索一圈
	ch[x][y] = '*';//dfs中进行的操作步骤
	/*dfs中的步进递归步骤*/
	for (int i = 0; i < 4; i++) {
		int newx = x + dx[i];
		int newy = y + dy[i];
		dfs(newx, newy);
	}

}
int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ch[i][j];
		}
	}
	dfs(0, 0);//从边界出发
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if(ch[i][j]=='0')
				s++;
		}
	}
	cout << s;
}

完美通过！