爆0了,9MLE,1WA蒟蒻求助
查看原帖
爆0了,9MLE,1WA蒟蒻求助
158878
B1ade_楼主2021/3/2 21:27
#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
int x,y,xe,ye,n;
struct node
{
	int x,y,d;
};
queue<node>q;
int ne[4]={1,0,-1,0},nx[4]={0,1,0,-1},minn[1005][1005];
int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
	{
		string st;cin>>st;
		for (int j=1;j<=n;++j)
		{
			a[i][j]=st[j-1]-'0';
		}
	}
	cin>>x>>y>>xe>>ye;
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) minn[i][j]=INT_MAX;
	node n11;n11.d=0;n11.x=1;n11.y=1;
	q.push(n11);
	while (q.size())
	{
		if (q.front().x==xe&&q.front().y==ye)
		{
			break;
		}
		for (int i=0;i<4;++i)
		{
			int xx=q.front().x+ne[i],yy=q.front().y+nx[i];
			if (xx>=1&&xx<=n&&yy>=1&&yy<=n&&!a[xx][yy]&&q.front().d+1<=minn[xx][yy])
			{
				node n12;n12.x=xx;n12.y=yy;n12.d=q.front().d+1;minn[xx][yy]=n12.d;
				q.push(n12);
			}
		}
		q.pop();
	}
	cout<<q.front().d;
	return 0;
}
2021/3/2 21:27
加载中...