BFS与MLE求助
查看原帖
BFS与MLE求助
738168
wang0728楼主2024/8/8 21:16
#include <bits/stdc++.h>
using namespace std;
struct f{
	int x,y;
}qi,zhong;
int n,dis[1005][1005];
char s;
bool vis[1005][1005];
queue<f>q;
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
void bfs(){
	while(!q.empty()){
		f now=q.front(); q.pop();
		vis[now.x][now.y]=true;
		for(int i=0;i<4;i++){
			int xx=now.x+dx[i],yy=now.y+dy[i];
			if(xx<=0 || xx>n || yy<=0 || yy>n) continue;
			if(vis[xx][yy]==false){
				dis[xx][yy]=dis[now.x][now.y]+1;
				if(xx==zhong.x && yy==zhong.y) return;
				q.push({xx,yy});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>s;
			if(s=='1') vis[i][j]=true;
		}
	}
	cin>>qi.x>>qi.y>>zhong.x>>zhong.y;
	q.push({qi.x,qi.y});
	vis[qi.x][qi.y]=true;
	bfs();
	cout<<dis[zhong.x][zhong.y];
	return 0;
}
2024/8/8 21:16
加载中...