题解 | 迷宫寻路

#include <iostream>
#include <vector>
using namespace std;

//深度优先搜索算法对(1,1)的邻近格子进行染色(矩阵值置为2)
void dfs(int i, int j, vector<vector<int>>& v){
    int n = v.size();
    int m = v[0].size();
    v[i][j] = 2;
    if(i >= 1 && v[i - 1][j] == 0){
        v[i - 1][j] = 2;
        dfs(i - 1, j, v);
    }
    if(i < n - 1 && v[i + 1][j] == 0){
        v[i + 1][j] = 2;
        dfs(i + 1, j, v);
    }
    if(j >= 1 && v[i][j - 1] == 0){
        v[i][j - 1] = 2;
        dfs(i, j - 1, v);
    }
    if(j < m - 1 && v[i][j + 1] == 0){
        v[i][j + 1] = 2;
        dfs(i, j + 1, v);
    }
}

int main() {
    //输入数据
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n,vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char tmp;
            cin >> tmp;
            if(tmp == '#'){
                v[i][j] = 1;
            }
        }
    }
    dfs(0, 0, v);//深度优先搜索染色
    //检查v[n - 1][m - 1]的值输出结果
    if(v[n - 1][m - 1] == 2){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")