电子老鼠闯迷宫

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

---

代码

#include<stdio.h>

#include<iostream>

using namespace std;

const int dx[5]={0,0,-1,0,1};

const int dy[5]={0,-1,0,1,0}; //四个可延伸的点

int n,x1,y1,x2,y2,a[1005][1005],fa[1005],st[1005][2],ans,last;

int check(int x,int y){ //判断这个点能不能延伸

	if(x>0 and x<=n and y>0 and y<=n)

	 if(a[x][y]==0)return 1;

	return 0;

}

void print(int x){ //输出

	if(x==0)return ;

	ans++;

	print(fa[x]);

	if(x!=last)

	 printf("(%d,%d)->",st[x][0],st[x][1]);

	  else printf("(%d,%d)\n",st[x][0],st[x][1]);  

}

void bfs(){

	int head=0,tail=1;

	st[1][0]=x1;st[1][1]=y1;

	fa[1]=0;

	do{

		head++;

		for(int i=1;i<=4;i++){

			if(check(st[head][0]+dx[i],st[head][1]+dy[i])){

				tail++;

				fa[tail]=head; //入队

				st[tail][0]=st[head][0]+dx[i];

				st[tail][1]=st[head][1]+dy[i];

				a[st[tail][0]][st[tail][1]]=1; //标记为走过的

			}

			if(st[head][0]==x2 and st[tail][1]==y2){ //判断有没有到达终点

				last=tail;

				print(tail);

				printf("%d",ans);

				return ;

			}

		}

	}while(head<=tail);

}

int main(){

	scanf("%d",&n);

	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=n;j++)

	  scanf("%d",&a[i][j]);

	bfs();

	return 0;

}