60求调

B3625 迷宫寻路

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,回溯同理(求关


|