求助,为什么会超时
查看原帖
求助,为什么会超时
672715
Cc_sir楼主2022/2/15 18:08
#include<iostream>
#include<queue>
using namespace std;
int n,x1,y1,x2,y2;
char aa[1005][1005];
bool bb[1005][1005];
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>aa[i][j];
		}
	}
	cin>>x1>>y1>>x2>>y2;
	queue<int>q,q1,q2;
	q.push(x1);
	q1.push(y1);
	q2.push(0);
	while(!q.empty())
	{
		if(q.front()==x2&&q1.front()==y2)
		{
			cout<<q2.front();
			break;
		}
		else
		{
			bb[q.front()][q1.front()]=1;
		for(int i=0;i<4;i++)
		{
			int nx=xx[i]+q.front();
			int ny=yy[i]+q1.front();
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&aa[nx][ny]=='0'&&bb[nx][ny]==0)q.push(nx),q1.push(ny),q2.push(q2.front()+1);
		}
		q.pop();
		q1.pop();
		q2.pop();
		}
	}
	return 0;

}

2022/2/15 18:08
加载中...