ycx303 @ 2025-01-05 21:35:08
BFS写的，求解！！！！
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int mark[N][N];
char map[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, m, ans;
void bfs() {
memset(mark, -1, sizeof mark);
queue <PII> q;
q.push({0, 0});
mark[0][0] = 0;
while (!q.empty()) {
PII top = q.front();
for (int i = 0; i < 4; i++) {
int nex = top.first + dx[i], ney = top.second + dy[i];
if (nex >= 0 && nex < n && ney >= 0 && ney < m && mark[nex][ney] == -1 && map[nex][ney] == 0) {
mark[nex][ney] = mark[top.first][top.second] + 1;
q.push({nex, ney});
}
}
q.pop();
}
cout << "Yes";
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%c", &map[i][j]);
}
}
bfs();
return 0;
}by 4041nofoundGeoge @ 2025-01-07 20:29:10
@ycx303不合法不输出。
by Max_robot @ 2025-01-08 12:50:35
@ycx303
给你一个歪解（如果想要正解就私信我）
#include<bits/stdc++.h>
using namespace std;
long long n, m;
char a[1010][1010];
bool dp[1010][1010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
dp[1][1]=true;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#') continue;
if(i==1 && j==1) continue;
if(dp[i][j-1] || dp[i-1][j] ||
dp[i+1][j] || dp[i+1][j]) dp[i][j]=true;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#') continue;
if(i==1 && j==1) continue;
if(dp[i][j-1] || dp[i-1][j] ||
dp[i+1][j] || dp[i+1][j]) dp[i][j]=true;
}
}
if(dp[n][m]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}