离开中山路

题目描述
爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？
输入格式
第1行：一个数 n
第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）
第n+2行：四个数 x1,y1,x2,y2
输出格式
只有1行：最短到达目的地距离
输入输出样例
输入
3
001
101
100
1 1 3 3
输出
4
分析
这道题我们可以用深搜（BFS）来做
十分简单，就是个队列，可以参考
电子老鼠闯迷宫（BFS）
来做
AC代码

#include<iostream>
int n,x1,y1,x2,y2,head,tail,a[1005][1005],st[1000005][3];
int dx[9]={
   0,1,-1,0,0};
int dy[9]={
   0,0,0,1,-1};
char ch;
void bfs()
{
   
	while(head<tail)//套广搜模板
	{
   
		head++;
		for(int i=1;i<=4;i++)//四个方向
		 {
   
		 	int x=st[head][0]+dx[i],y=st[head][1]+dy[i];
		 	if(x>=1&&x<=n&&y>=1&&y<=n)//边界
		 	 if(a[x][y]==0)//是否判断过
		 	  {
   
		 	  	tail++;
		 	  	a[x][y]=1;//标记
		 	  	st[tail][2]=st[head][2]+1;//最短路径
			    st[tail][0]=x;st[tail][1]=y;//更新坐标
			    if(x==x2&&y==y2)return;//如果到目标点就退出
			  }
		 }
	}
}
using namespace std;
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  {
   cin>>ch;a[i][j]=ch-48;}//输入
	cin>>x1>>y1>>x2>>y2;
	st[1][0]=x1;st[1][1]=y1;//坐标
	a[x1][y1]=1;//标记
	tail=1;//初值
	bfs();
	cout<<st[tail][2];
}

谢谢