错一个点求助(01bfs)
查看原帖
错一个点求助(01bfs)
66964
heyuguo楼主2024/6/12 20:13

#include<bits/stdc++.h>
using namespace std;
long long h,w,sc,sr,ec,er;
char c[1050][1050];
struct node
{
	long long x,y;
};
deque<node> q;
long long dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},dis[1050][1050];
void bfs()
{
	q.push_back({sc,sr});
	dis[sc][sr]=0;
	while(!q.empty())
	{
		node u=q.front();
		q.pop_front();
//		if(u.x==ec&&u.y==er)return;
		for(int i=0;i<4;i++)
		{
			long long nx=u.x+dx[i],ny=u.y+dy[i];
			if(nx>0&&ny>0&&nx<=h&&ny<=w&&dis[nx][ny]>dis[u.x][u.y]&&c[nx][ny]=='.')
			{
				dis[nx][ny]=dis[u.x][u.y];
				q.push_front({nx,ny});
			}
		}
		for(int i=-2;i<=2;i++)
		{
			for(int j=-2;j<=2;j++)
			{
				long long nx=u.x+i,ny=u.y+j;
				if(nx>0&&ny>0&&nx<=h&&ny<=w&&dis[nx][ny]>dis[u.x][u.y]+1&&c[nx][ny]=='.')
				{
					dis[nx][ny]=dis[u.x][u.y]+1;
					q.push_back({nx,ny});
				}
			}
		}
	}
}
int main()
{
//	ios::sync_with_stdio(0);
	cin>>h>>w>>sc>>sr>>ec>>er;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
			cin>>c[i][j];
	}
	memset(dis,0x3f,sizeof dis);
	bfs();
	if(dis[ec][er]<=10000)
		cout<<dis[ec][er];
	else
		cout<<-1;
	return 0;
}
2024/6/12 20:13
加载中...