RedLotus_Resolution @ 2022-08-24 19:31:45
#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;
}by williamwei @ 2022-08-24 19:48:28
你最好不要用结构体，换用dis数组即可。vis可以去掉。在bfs到达终点后直接输出yes并退出
by RedLotus_Resolution @ 2022-08-25 16:30:08
@williamwei 那你能不能看下整体框架有没有什么问题，因为WA4个点
by williamwei @ 2022-08-27 19:24:30
@mashiwen36 我把AC代码发你吧。前面没看到
by williamwei @ 2022-08-27 19:27:53
过会发。现在不在电脑旁
by williamwei @ 2022-08-31 12:47:24
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 105;
int n, m;
char s[maxn][maxn];
const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
bool vis[maxn][maxn];
#define POSIN(x,y) (x>=0&&x<n&&y>=0&&y<m)
void bfs() {
queue<pair<int,int>> q;
q.push({0,0});
while (q.empty() ^ 1) {
int x = q.front().first, y = q.front().second; q.pop();
if (x == (n - 1) && y == (m - 1)) {
cout << "Yes";
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!POSIN(nx, ny) || vis[nx][ny] || s[nx][ny]=='#') continue;
vis[nx][ny] = true;
q.push({ nx,ny });
}
}
cout << "No";
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> s[i];
bfs();
}