题解 | #迷宫问题#

#include <iostream>
#include <vector>

using namespace std;

/*递归寻路函数
x,y为起始点坐标，N,M为图尺寸
将地图上走过的路径点的值更改为2
并将正确路线途径坐标的值更改为3*/
bool find(int x, int y, vector<vector<int>>* map, int N, int M) {
    if ((*map)[x][y] == 0) {
        (*map)[x][y] = 2;
    }
    if (x == N - 1 && y == M - 1) {
        (*map)[x][y] = 3;
        return true;
    }
    if (x < N - 1 && (*map)[x + 1][y] == 0) {
        if (find(x + 1, y, map, N, M) == true) {
            (*map)[x][y] = 3;
            return true;
        }
    }
    if (y < M - 1 && (*map)[x][y + 1] == 0) {
        if (find(x, y + 1, map, N, M) == true) {
            (*map)[x][y] = 3;
            return true;
        }
    }
    if (x > 0 && (*map)[x - 1][y] == 0) {
        if (find(x-1, y, map, N, M) == true) {
            (*map)[x][y] = 3;
            return true;
        }
    }
    if (y > 0 && (*map)[x][y - 1] == 0) {
        if (find(x, y - 1, map, N, M) == true) {
            (*map)[x][y] = 3;
            return true;
        }
    }
    return false;
}

//从起始点依次输出标记为3的路径点
void route(int x, int y, vector<vector<int>>* map, int N, int M) {
    cout << "(" << x << ',' << y << ')' << endl;
    (*map)[x][y] = 4;   //对已经输出的坐标进行标记
    if (x < N - 1 && (*map)[x + 1][y] == 3) {
        route(x + 1, y, map, N, M);
    }
    if (y < M - 1 && (*map)[x][y + 1] == 3) {
        route(x, y + 1, map, N, M);
    }
    if (x > 0 && (*map)[x - 1][y] == 3) {
        route(x - 1, y, map, N, M);
    }
    if (y > 0 && (*map)[x][y - 1] == 3) {
        route(x, y - 1, map, N, M);
    }
}

int main() {
    int N = 0, M = 0;
    cin >> N;
    cin >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
    find(0, 0, &map, N, M);
    route(0, 0, &map, N, M);
}