【蓝桥杯】2015决赛B组 5 穿越雷区（深度优先搜索dfs、广度优先搜索bfs）—— 酱懵静

历届试题 穿越雷区

问题描述
X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。

例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。

数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。
要求输出一个整数，表示坦克从A区到B区的最少移动步数。如果没有方案，则输出-1

例如：
用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
则程序应该输出：10

---

——分析——

---

分析：
本题也是在学习了搜索算法的相关知识后必须刷的经典例题
这道题的经典之处在于两点：
1.改变了传统走迷宫的固定模式
2.两种搜索算法都可使用
下面来一一介绍与分析

---

——分析1：广度优先搜索——

---

首先介绍广度优先搜索算法
通常情况下看到“求最短路径”字样的题时，我们应该想到的第一个算法都是bfs。这个算法的特点是不一定会将整个地图遍历完，而是直接在一个队列中进行迭代操作进而找到最短路径，并且没有递归调用函数，因此在求最短路径的时候其时间开销相对还是较短的。
在本题中，我们的解题思路与其他的走迷宫算法基本一致，唯一不同的在于“必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转”，即我们的算法中，在判断下一个点能否走时有两个点要被考虑，一个是该点是否走过，另一个是该点的能量是否与当前点的能量相异。只有当这两个都满足的时候才能走。
由于本题难度并不是很大，下面直接给出用bfs算法解决本题的完整代码：

#include<iostream>
#include<queue>
using namespace std;

const int MAX=105;
int n;
char map[MAX][MAX];
bool vis[MAX][MAX]; 
int go[][2]={{1,0},{0,-1},{0,1},{-1,0}};//四个可行走方向 

struct Point
{
	int x,y,step;
	Point(int a,int b,int c)
	{ x=a,y=b,step=c; }
};

void bfs(int x,int y)
{
	queue<Point> q;
	Point p(x,y,0);
	q.push(p);
	vis[x][y]=true;
	while(!q.empty())
	{
		Point temp=q.front();q.pop();
		for(int i=0;i<4;i++)
		{
			int new_x=temp.x+go[i][0],new_y=temp.y+go[i][1];
			if(new_x>=1 && new_x<=n && new_y>=1 && new_y<=n
			&& !vis[new_x][new_y] && map[temp.x][temp.y]!=map[new_x][new_y])
			{
				if(map[new_x][new_y]=='B'){ 
					cout<<temp.step+1<<endl;
					return; 
				}
				vis[new_x][new_y]=true;		//标记为已走 
				q.push(Point(new_x,new_y,temp.step+1));
			}
		}
	}
	//如果队列中所有点都走完了也没能找到一个最短的移动方案就直接输出-1
	cout<<-1<<endl;
}

int main()
{
	int start_x,start_y;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='A')
				start_x=i,start_y=j;
		}
	bfs(start_x,start_y);
	return 0;
}

---

——分析2：深度优先搜索——

---

接下来介绍深度优先搜索算法
深度优先搜索算法的特点是以递归的方式对地图进行遍历，其存在回溯的过程，因此会遍历完图中的所有情况。而我们要解本题，正好要用到dfs算法的这一特性。由于dfs算法会遍历完所有的情况，故我们的解题思路就是直接暴力搜索得到所有的结果，然后取出其中的最小值。虽然说遍历完所有的情况看起来确实很棒，但实际上这样的下场是极易超时。也就是说对题中所给的数据范围非常敏感。
本题中的方阵最大会达到99，这个范围对于dfs算法而言显然是非常大的，这在程序的dfs过程中会使得递归树过于深，从而导致超时的出现。因此就必须对dfs算法进行剪枝。
剪枝的主要思路是提前截断。什么意思？比如说某一次遍历得到了从起点到终点的步数为12，当然，此时并没有完全结束，dfs还会继续执行下去以寻求更小的答案。于是开始回溯，并往其他路线搜索。假设当前搜索到了某个点，且此时的步数为13，那么就意味着再从这个点继续搜索下去就算能够找到终点出去，那这条路线的长度也一定会大于等于13，这样的搜索显然是无意义的，因为已经找到了一个比13更小的路线。因此，我们的提前截断就是指在当前某个点的步数大于了之前已经得到了的某个步数后，就直接回溯，从而降低内存开销并加快搜索的速度。

同样地，下面直接给出用dfs算法解决本题的完整代码：

#include<iostream>
using namespace std;

const int MAX=105;
int n,ans=100000000; 
char map[MAX][MAX];
bool vis[MAX][MAX]; 
int go[][2]={{1,0},{0,-1},{0,1},{-1,0}};//四个可行走方向 

void dfs(int x,int y,int step)
{
	if(step>=ans) return;	//剪枝：没必要再走下去了，反正即使可达也不会是最短路径了
	if(map[x][y]=='B')
	{
		ans=step;
		return;
	} 
	vis[x][y]=true;			//标记为已走 
	for(int i=0;i<4;i++)
	{
		int now_x=x+go[i][0],now_y=y+go[i][1];
		if(now_x>=1 && now_x<=n && now_y>=1 && now_y<=n
		&& !vis[now_x][now_y] && map[x][y]!=map[now_x][now_y] )
			dfs(now_x,now_y,step+1); 
	}
	vis[x][y]=false;		//回溯过程中还原 
}

int main()
{
	int start_x,start_y; 
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='A')
				start_x=i,start_y=j;
		}
	dfs(start_x,start_y,0);
	if(ans==100000000) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}