wyxrl @ 2024-08-19 11:05:14
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+1;
int n,m;
int dx[]={-1,0,1,0},
dy[]={0,1,0,-1};
char Map[101][101];
bool Mark[101][101];
bool flag=false;
void DFS(int x,int y){
if(x==n&&y==m){
flag=true;
return;
}
for(int j=0;j<4;j++){
int tx=x+dx[j],
ty=y+dy[j];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(Map[tx][ty]=='.'&&Mark[tx][ty]==false){
Mark[tx][ty]=true;
DFS(tx,ty);
Mark[tx][ty]=false;
}
}
}
int main (){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>Map[i][j];
}
}
DFS(1,1);
if(flag) cout<<"Yes";
else cout<<"No";
return 0;
}
by lovely_codecat @ 2024-08-20 14:42:20
@zbxssm 因为它只是问你能不能到,不问你最短路
by zbxssm @ 2024-08-20 16:05:37
@lovely_codecat 但我不回溯的话不就相当于只能走一条路径了吗,要是走到死胡同怎么办啊
by lovely_codecat @ 2024-08-20 17:22:26
@zbxssm 不是,只是相当于你走过的路不能在走
by zbxssm @ 2024-08-20 22:20:24
@lovely_codecat 那个我找路径条数不是要回溯吗,这里要是进了死胡同不是要换一条看其他路能不能走吗
by lovely_codecat @ 2024-08-21 07:18:00
@zbxssm 是,但是那只是函数本身的回溯,不用清空标记数组
by Stockfish_ @ 2024-08-22 19:19:41
@lovely_codecat cin函数应该不会读,scanf才会读