60

B3625 迷宫寻路

_O__o_ @ 2023-11-10 15:29:02

#include<bits/stdc++.h>

using namespace std;
bool mapp[111][111];
int dir[4][2] = {
    1,0,
    0,1,
    -1,0,
    0,-1
};
bool flagg;
int n,m;
void dfs(int x,int y){
    if(x == n && y == m)
        flagg = 1;
    if(flagg)
        return;
    for(int i = 0;i < 4;i++){
        int xx = x + dir[i][0],
            yy = y + dir[i][1];
        if(xx > 0 && xx <= n && yy > 0 && yy <= m && mapp[xx][yy]){
            if(mapp[xx][yy] == 0)
                return;
            mapp[xx][yy] = 0;
            dfs(xx,yy);
            mapp[xx][yy] = 1;
        }
    }
    return;
}
signed main(){
    //step 1. 读题、声明变量

    //step 2. 输入
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            char a; 
            cin >> a;
            if(a == '.')
                mapp[i][j] = 1;
            else
                mapp[i][j] = 0; 
        }
    }
    //step 3. 处理
    if(mapp[1][1] == 0)
        return 0;
    if(mapp[n][m] == 0)
        return 0;
    dfs(1,1);
    //step 4. 输出
    if(flagg)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

by lululu693 @ 2023-11-15 15:37:56

mapp[xx][yy] = 1;注释掉,走过就标记上,后面就不走了,找一条道就可以


|