Forest（BFS算法经典例题 ）C++代码

Long long ago，有一片大大的森林，据可靠情报，森林中埋有宝藏，森林的形状很奇怪，是正方形的。

为了方便起见，森林的每一个都有一个坐标，例如样例图中左上角的点为（1，1），右下角的点为（5，5）。森林中有很多地方有大树，这些地方是不能走的，用白色格子表示；可以走的地方有黑色格子表示。 现在你可以从森林边缘的任意一个点出发，向八个方向，走向埋宝藏的地方（宝藏的坐标是事先给定的）。为了抢在其他人之前夺取宝藏，你要走一条最短路，那么，你花费的时间最少是多少呢？

包含N+2行，第一行一个整数N（N<=5000），说明森林的大小；第二行两个整数x,y，表示宝藏的坐标。接下来N行，描述这个森林，"#"表示黑色，"."表示白色。

只包含一个整数，即到达宝藏处的最短时间。如果无解，输出"No solution"。

输入 #1

5
3 3
##...
#....
#.#..
.#...
..###

输出 #1

3

有两种走法： (3,1)->(4,2)->(3,3) (5,3)->(4,2)->(3,3) 最短时间为3。 对于40%的数据，N<=50 对于100%的数据，N<=5000

很显然，这是一道广度优先搜索的题目。题目大意是从任意一边出发，经过最少的步数到达埋宝藏的地点，而且要绕过障碍。如果我们枚举每一个边缘的点进行搜索最少步数，那么我们的时间复杂度将会达到一个极其庞大的地步恐怕连40%的数据样例都过不了，于是我们找到了一种更为优秀的算法：

既然题目要求的是边缘点—>藏宝点，那么可不可以换个思路，将搜索顺序改为藏宝点—>边缘点呢？

答案显然是“可以”。

我们只需将藏宝点设为搜索起始点，在搜索过程中只要遇到边缘点就停止搜索，并将最少步数输出就可以了。

#include
using namespace std;
int n,zx,zy,he=1,ta=1;//森林大小、终点的横纵坐标、队头、队尾。
int dx[9]={0,0,0,-1,1,1,-1,-1,1};//方向数组1
int dy[9]={0,-1,1,0,0,1,-1,1,-1};//方向数组2
bool p[10001][10001];//判断各个点有没有被访问过。
struct map
{
	int x;//横坐标
	int y;//纵坐标
	int st;//步数
}a[101];
//结构体map
int main()
{
	cin>>n>>zx>>zy;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char x;
			cin>>x;
			if(x=='#')
			{
				p[i][j]=1;//判断能不能走，p数组为0时不能走（无论是有障碍或者是走过了）
			}
            if(i==zx&&j==zy&&p[i][j]==0)//剪枝，如果藏宝点有障碍，直接无解。
            {
                cout<<"No solution"<n*n)//如果步数超过了森林大小就说明有重复的，直接无解
        {
            cout<<"No solution"<