救救孩子,BFS 80昏
查看原帖
救救孩子,BFS 80昏
1412841
BaiBaiShaFeng楼主2024/11/26 17:22
#include <bits/stdc++.h>
using namespace std;
int n, m;
char ma[114][114];
bool f=false;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct Point{
	int x, y;
};
bool vis[114][114];
deque <Point> q;
void bfs(int px, int py){
	Point st;
	st.x=px;
	st.y=py;
	vis[px][py]=1;
	q.push_back(st);
	while(!q.empty()){
		Point nw=q.front();
		if(nw.x==m&&nw.y==n){
			f=true;
		}
		for(int i=1; i<=3; i++){
			Point next=nw;
			next.x+=dx[i];next.y+=dy[i];	
			if(ma[next.x][next.y]=='#'||vis[next.x][next.y]==1){
				continue;
			}
			vis[next.x][next.y]==1;
		}
		q.pop_front();
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0; i<=110; i++){for(int j=0; j<=110; j++){ma[i][j]='#';}}
	for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){scanf("%c",&ma[j][i]);}}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(ma[j][i]=='.'&&vis[j][i]!=true){
				bfs(j,i);
			}
		}
	}
	if(f==true){
		cout<<"Yes";return 0;
	}
	cout<<"No";
	return 0;
}

本蒟蒻刚学bfs,改半天不对;

2024/11/26 17:22
加载中...