[C++知识库]信奥1215：迷宫(详解标记数组的还原)

【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n
的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n(1≤n≤100)，表示迷宫的规模是n×n的。接下来是一个n×n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha,la,hb,lb全部是从0开始计数的。

【输出】
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

最初的写法（超时了）

刚开始没有多想，就用dfs去做了，代码如下：

#include<bits/stdc++.h>
using namespace std;

int k, n;
char a[105][105]; //地图 
int b[105][105]; //标记数组 
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //方向数组 
int startx, starty, endx, endy;
bool flag;

void dfs(int x, int y) {
	//递归出口
	if (x == endx && y == endy) {
		cout << "YES" << endl;
		flag = true;
		return;
	}
	
	//递归条件
	for (int i = 0; i < 4; i++) {
		int nextx = x + d[i][0];
		int nexty = y + d[i][1];
		if (nextx >= 0 && nexty >= 0 && nextx < n && nexty < n && a[nextx][nexty] == '.' && !b[nextx][nexty]) {
			//没越界、没有障碍物、没走过，同时满足三者才可以走
			b[nextx][nexty] = 1;
			dfs(nextx, nexty);
			b[nextx][nexty] = 0; 
		}
	} 
}

int main()
{
	cin >> k;
	for (int i = 0; i < k; i++) {
		//初始化工作 
		memset(a, 0, sizeof(a)); 
		memset(b, 0, sizeof(b)); 
		
		//输入地图维度 
		cin >> n;
		
		//输入地图
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n; col++) {
				cin >> a[row][col];
			}
		} 
		
		//输入起点终点
		cin >> startx >> starty >> endx >> endy;
		
		//特判
		if (a[startx][starty] == '#' || a[endx][endy] == '#') { //起点或终点为# 
			cout << "NO" << endl;
			continue;
		} 
		
		flag = false;
		b[startx][starty] = 1;
		dfs(startx, starty);
		if (flag == false) cout << "NO" << endl;
	}
	return 0;
}

结果超时了…

超时写法原因总结

通过与大佬交流后发现，此题回溯时不需要还原标记数组。那么问题来了，为什么不用还原标记数组呢？

是的，最初接触深搜回溯算法时我们经常会写这样的代码：

//b为标记数组
b[x] = 1; //标记已经走过
dfs(); //深搜
b[x] = 0; //回溯并还原标记数组

但是我们要知道这种写法对应的题目要求一般是这样的：“寻找最短路径”、“求总方案数”、“列出所有方案”等。这种就要求我们穷尽所有情况。比如我们一条路走不通了，那么我们回去，而且在我们回去之后，我们以后还是可以经过这条路的，因为我们已经在回溯的过程中还原了标记数组，形象来说就是我们抹除了我们走过这里的记忆，所以以后有可能还会来这儿。

但是对于像本题这种题，我们一般这样写：

//b为标记数组
b[x] = 1; //标记已经走过
dfs(); //深搜

这种对应的题目一般是“是否能走到”、“有无一种方案能够到达”等。因为我们的目的是找到终点，所以不需要像上面那样穷尽所有的方案，我们只要找到了，那么就停止搜索了。比如我们一条路走不通了，那么我们回去，并且在回去的路上，我们用土把这些走过的地方填上，以后就不走这儿了（这条路找不到终点那我以后还走这儿干嘛！？）。直到我们找到终点，那么搜索就停止了。这样写之所以不会超时，是因为我们把那些走过的路都填上了 ，以后就不会再走了，降低了复杂度。

正确写法

其实就是把b[nextx][nexty] = 0;注释掉就行。

#include<bits/stdc++.h>
using namespace std;

int k, n;
char a[105][105]; //地图 
int b[105][105]; //标记数组 
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //方向数组 
int startx, starty, endx, endy;
bool flag;

void dfs(int x, int y) {
	//递归出口
	if (x == endx && y == endy) {
		cout << "YES" << endl;
		flag = true;
		return;
	}
	
	//递归条件
	for (int i = 0; i < 4; i++) {
		int nextx = x + d[i][0];
		int nexty = y + d[i][1];
		if (nextx >= 0 && nexty >= 0 && nextx < n && nexty < n && a[nextx][nexty] == '.' && !b[nextx][nexty]) {
			//没越界、没有障碍物、没走过，同时满足三者才可以走
			b[nextx][nexty] = 1;
			dfs(nextx, nexty);
			//b[nextx][nexty] = 0; 
		}
	} 
}

int main()
{
	cin >> k;
	for (int i = 0; i < k; i++) {
		//初始化工作 
		memset(a, 0, sizeof(a)); 
		memset(b, 0, sizeof(b)); 
		
		//输入地图维度 
		cin >> n;
		
		//输入地图
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n; col++) {
				cin >> a[row][col];
			}
		} 
		
		//输入起点终点
		cin >> startx >> starty >> endx >> endy;
		
		//特判
		if (a[startx][starty] == '#' || a[endx][endy] == '#') { //起点或终点为# 
			cout << "NO" << endl;
			continue;
		} 
		
		flag = false;
		b[startx][starty] = 1;
		dfs(startx, starty);
		if (flag == false) cout << "NO" << endl;
	}
	return 0;
}

相似练习题

可以看一下这道题，也是不需要还原标记数组的。