走迷宫

解题思路

一道bfs模板

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,x1,y1,x2,y2,head,tail,px[1000005],py[1000005],a[1005][1005],sum[1005][1005];
int dx[4]={
   0,0,1,-1};//四个方向
int dy[4]={
   1,-1,0,0};
bool check(int x,int y)//判断
{
   
	if(x>=1&&x<=n&&y>=1&&y<=n)
	 if(!a[x][y])return 1;
	return 0;
}
void bfs(int x,int y)//bfs
{
   
	px[++tail]=x;//初值
	py[tail]=y;
	while(head<tail)
	{
   
		head++;
		for(int i=0;i<4;i++)
		{
   
			int xx=px[head]+dx[i],yy=py[head]+dy[i];//移动后的位置
			if(check(xx,yy))
			{
   
				a[xx][yy]=1;
				px[++tail]=xx;
				py[tail]=yy;
				sum[xx][yy]=sum[px[head]][py[head]]+1;
				if(xx==x2&&yy==y2)//到了目标点就输出
				{
   
					printf("%d",sum[xx][yy]);
					return;
				}
			}
		}
	}
}
int main()
{
   
	scanf("%d",&n);//输入
	for(int i=1;i<=n;i++)
	{
   
		string s;
		cin>>s;
	 	for(int j=0;j<n;j++)a[i][j+1]=s[j]-48;
	}
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	bfs(x1,y1);  
	return 0;
}

谢谢