电子老鼠闯迷宫

Description
如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。

Input

Output

Sample Input
12 //迷宫大小
2 9 11 8 //起点和终点
1 1 1 1 1 1 1 1 1 1 1 1 //邻接矩阵，0表示通，1表示不通
1 0 0 0 0 0 0 1 0 1 1 1
1 0 1 0 1 1 0 0 0 0 0 1
1 0 1 0 1 1 0 1 1 1 0 1
1 0 1 0 0 0 0 0 1 0 0 1
1 0 1 0 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1 0 0 0 0 1
1 0 1 1 1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0 0 0 0 1
1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1

Sample Output
(2,9)->(3,9)->(3,8)->(3,7)->(4,7)->(5,7)->(5,6)->(5,5)->(5,4)->(6,4)->(7,4)->(7,3)->(7,2)->(8,2)->(9,2)->(9,3)->(9,4)->(9,5)->(9,6)->(8,6)->(8,7)->(8,8)->(9,8)->(9,9)->(10,9)->(11,9)->(11,8)
27

分析
这题可以用深搜或者广搜，我这里采用广搜
我们知道从起点开始，一直到终点，一个点一个点去找，最后求出结果，再递归回去输出，就行了

AC代码

#include<iostream>
using namespace std;
int dx[5]={
   0,1,-1,0,0};
int dy[5]={
   0,0,0,1,-1};
int x1,y1,x2,y2,n,a[1005][1005],st[1005][3],fa[1005],head,tail,s;
bool check(int x,int y)//判断是否符合条件
{
   
	if(x>=1&&x<=n&&y>=1&&y<=n)//边界判断
	 if(a[x][y]==0) return true;//是否出现过
	return false; 
}
void work(int x)//输出
{
   
	if(x==0) return;
	s++;
	work(fa[x]);//递归
	if(x!=tail)//最后一个不能输出“->”
	cout<<"("<<st[x][1]<<","<<st[x][2]<<")"<<"->"; 
	else 
	cout<<"("<<st[x][1]<<","<<st[x][2]<<")"<<endl;
}
void bfs()
{
   
	tail=1;//尾巴初始值为1
	a[x1][y1]=1;//已经到过这里
	st[1][1]=x1;st[1][2]=y1;//坐标
	fa[1]=0;//父节点
	do//广搜
	{
   
		head++;//头加1
		for(int i=1;i<=4;i++)//四个方向延伸
		 if(check(st[head][1]+dx[i],st[head][2]+dy[i]))
		 {
   
		 	tail++;
			st[tail][1]=st[head][1]+dx[i];//更新坐标
			st[tail][2]=st[head][2]+dy[i];
			fa[tail]=head;//父节点
			a[st[tail][1]][st[tail][2]]=1;		
		 	if(st[tail][1]==x2&&st[tail][2]==y2)//判断是否到终点
		 	{
   
		 		work(tail);
		 		cout<<s;
		 		return;
		 	}
		 } 
	}while(head<=tail);
}
int main()
{
   
	cin>>n;
	cin>>x1>>y1>>x2>>y2;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  cin>>a[i][j];
	bfs();//调用
}

谢谢观看