Oliver的救援（BFS）

Oliver的救援

Description
在你的帮助下，Oliver终于追到小X了，可有一天，坏人把小X抓走了。这正是Oliver英雄救美的时候。所以，Oliver又找到哆啦A梦，借了一个机器，机器显示出一幅方格地图，它告诉Oliver哪里能走，哪里不能走,。并且Oliver在这个地图的右下角(x,y) ，而小X在左上角 (x1,y1)。时间紧急，Oliver想知道，最少要走多少个格子,才能找到小X。（只能直走）。

Input
共N+1行，第一行为N，以下N行N列0-1矩阵，1表示不能通过,0表示可以通过(左上角和右下角为0). N<=30n<=1000 .

Output
共一个数，为最少的走的格子数.

Sample Input
5
0 1 1 1 1
0 0 1 1 1
1 0 0 0 1
1 1 1 0 1
1 1 1 0 0
5 5 1 1

Sample Output
9

错误

1.这题的测试数据其实是有，起始点和终点的，但是，题目没有说明白，所以正确的输入和输出应该是：
输入
5
0 1 1 1 1
0 0 1 1 1
1 0 0 0 1
1 1 1 0 1
1 1 1 0 0
5 5 1 1（这里前两个数是Oliver的位置（x,y），后面两个数是小X的位置（x1,y1））
输出
9

2.这题的数据点，n是小于等于1000的,正确应该是：
n<=1000

分析

这题是道模板题，我们可以用广搜BFS
可以根据电子老鼠闯迷宫
https://blog.csdn.net/weixin_45524309/article/details/103428660
来做

AC代码

#include<iostream>
using namespace std;
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int n,a[1001][1001],st[1000001][4],head,tail,x1,y1,x2,y2;
char b;
void bfs()
{
	tail=1;
	a[x1][y1]=1;
	st[1][1]=x1;st[1][2]=y1;//坐标
	do
	{
		head++;
		for(int i=1;i<=4;i++)//遍历4个方向
		{
		int x=st[head][1]+dx[i],y=st[head][2]+dy[i];
		 if(x>=1&&x<=n&&y>=1&&y<=n)
	      if(a[x][y]==0)
		 {
		 	tail++;
			st[tail][1]=x;//坐标
			st[tail][2]=y;
			st[tail][3]=st[head][3]+1;//最少步数
			a[x][y]=1;		//已走过
		 	if(x==x2&&y==y2)//到达终点
		 	{
		 		cout<<st[tail][3];
		 		return;
		 	}
		 }
		 } 
	}while(head<=tail);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  {
	   cin>>b;
	   a[i][j]=b-48;//字符输入
}
	cin>>x1>>y1>>x2>>y2;  
	bfs();
} 

谢谢观看