BFS蒟蒻求助
查看原帖
BFS蒟蒻求助
457431
Li_wenjie楼主2021/11/14 23:46
#include<bits/stdc++.h>
using namespace std;
int ans[1001][1001];
bool notok[1001][1001];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
struct Node
{
	int x,y;
	Node(int _x,int _y)
	{
		x=_x,y=_y;
	}
};
int main()
{
	memset(ans,-1,sizeof(ans));
//	cout<<ans[313][313];
	queue<Node> s;
	int n;
	cin>>n;
	int m=n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%1d",&notok[i][j]);
	int x,y,x1,y1;
	cin>>x>>y>>x1>>y1; 
	Node first(x,y);
	s.push(first);
	ans[x][y]=0;
	bool pd=0;
	while(!s.empty())
	{
		Node now=s.front();
		s.pop();
		int _x=now.x;
		int _y=now.y;
		int step=ans[_x][_y];
		for(int i=0;i<=7;i++)
		{
			int xx=_x+dx[i];
			int yy=_y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&ans[xx][yy]==-1&&!notok[xx][yy]) 
			{
				Node newnode(xx,yy);
				s.push(newnode);
				ans[xx][yy]=step+1;
			}
		}
	}
	cout<<ans[x1][y1];
}
2021/11/14 23:46
加载中...