蒟蒻广搜60分求助
查看原帖
蒟蒻广搜60分求助
598263
RedLotus_Resolution楼主2022/8/24 19:31
#include<bits/stdc++.h>
using namespace std;
long long n,m,l=0,r=1;
char c[505][505];
bool ctg[505][505];//障碍 
bool vis[505][505];//已经访问过 
int p[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct walk{
	long long x;//x坐标 
	long long y;//y坐标 
	bool reach;//能否到达一个点 
}w[10098];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='#'){
				ctg[i][j]=1;
			}
		}
	}
	w[1].x=1;
	w[2].y=1;
	//w[1].reach=1;这句要加吗?好像没什么影响 
	while(l<r){//广搜套模板 
		l++;
		for(int k=0;k<4;k++){
			long long nx=w[l].x+p[k][0];
			long long ny=w[l].y+p[k][1];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ctg[nx][ny]==0&&vis[nx][ny]==0){
				r++;
				vis[nx][ny]=1;
				w[r].x=nx;
				w[r].y=ny;
				w[r].reach=1;
				if(nx==n&&ny==m){
					if(w[r].reach==1){
						cout<<"Yes";
						return 0;
					}
					else{
						cout<<"No";
						return 0;
					}
				}
			}
		}
	}
	return 0;
}
2022/8/24 19:31
加载中...