RonL @ 2024-05-06 21:38:03
#include<bits/stdc++.h>
using namespace std;
int n,m;
char arr[105][105];
bool flag = false;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
bool vis[105][105] = {false};
void dfs(int x,int y){
int nx,ny;
if(x == n && y == m){
cout << "Yes";
exit(0);
}else{
for(int i=0;i<4;i++){
nx = x+dx[i];
ny = y+dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == false){
vis[nx][ny] = true;
dfs(nx,ny);
vis[nx][ny] = false;
}else{
continue;
}
}
return;
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> arr[i][j];
}
}
if(arr[1][1] == '#' || arr[n][m] == '#' || (arr[1][2] == '#' && arr[2][1] == '#')){
cout << "No";return 0;
}
dfs(1,1);
cout << "No";
return 0;
}
by Chu_awa_xing @ 2024-05-13 13:45:09
两个问题,第一:障碍#是有可能把终点包围起来的,所以在dfs函数里判断能否走的条件里加一个 arr[nx][ny]!='#'
第二vis数组标记应该标记当前格,也就是x和y,而不是nx和ny,回溯同理(求关