BFS,但只有40分
查看原帖
BFS,但只有40分
1074321
a_tall_bird楼主2024/3/5 18:36
#include<bits/stdc++.h>
using namespace std;
bool _map[999][999];
bool is_ok(int n,int m){
	queue<pair<int,int>> q;
	unordered_set<int> is_visit,not_visit;
	q.push({1,1});
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		if(x==n&&y==m){
			return 1;
		}
		if(x+1<=n&&is_visit.find(x+1)==is_visit.end()&&!_map[x+1][y]){
			q.push({x+1,y});
			is_visit.insert(x+1);
		}
		if(x-1>=1&&is_visit.find(x-1)==is_visit.end()&&!_map[x-1][y]){
			q.push({x-1,y});
			is_visit.insert(x-1);
		}
		if(y+1<=m&&not_visit.find(y+1)==not_visit.end()&&!_map[x][y+1]){
			q.push({x,y+1});
			not_visit.insert(y+1);
		}
		if(y-1>=1&&not_visit.find(y-1)==not_visit.end()&&!_map[x][y-1]){
			q.push({x,y-1});
			not_visit.insert(y-1);
		}
	}
	return 0;
}
int main(){
	int n,m;
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char s;
			cin>>s;
			if(s=='.')_map[i][j]=0;
			else _map[i][j]=1;
		}
	}
	bool ans=is_ok(n,m);
	if(ans)cout<<"Yes";
	else cout<<"No";
}
2024/3/5 18:36
加载中...