dfs 10分求助

B3625 迷宫寻路

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才会读


上一页 |