题解 | 迷宫问题

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
struct Corr {
    int x;
    int y;
    int level;    // 记录DFS层数
};
bool valid_step(Corr cor, vector<vector<int>> valid_matrix, int max_x, int max_y, int min_x = 0, int min_y = 0) {
    if ((cor.x < min_x) || (cor.y < min_y) || (cor.x > max_x) || (cor.y > max_y)) {
        return false;
    } else {
        if (valid_matrix[cor.y][cor.x] == 1) {
            return false;
        }
    }
    return true;
}    //判断当前步是否可行？
Corr move(Corr cur, int flag = 0) {
    Corr my;
    my.x = cur.x;
    my.y = cur.y;
    switch (flag) {
        case 0:
            my.x -= 1;   //左移
            break;
        case 1:
            my.x += 1;     //右移
            break;
        case 2:
            my.y -= 1;     //上移
            break;
        case 3:
            my.y += 1;      //下移
            break;
    }
    return my;
}
int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<int>> valid(h, vector<int>(w, 0));
    stack<Corr> S;   // 存储已经遍历的节点
    stack<Corr> R;   // 存储结果
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int valid_corr;
            cin >> valid_corr;
            valid[i][j] = valid_corr;
        }
    }
    Corr i;
    i.x = 0;
    i.y = 0;
    i.level = 0;
    S.push(i);    //初始化节点入栈
    while ((S.top().x != w - 1) || (S.top().y != h - 1)){
        Corr cur_pos = S.top();
        valid[cur_pos.y][cur_pos.x] = 1;   //记录已遍历的节点，防止重复回溯
        // cout<<cur_pos.y<<' '<<cur_pos.x<<endl;
    
        int possible = 0;
        int cur_level = cur_pos.level;
        // 满足条件的上下左右移入栈，下一层节点（可能的下一步）入栈
        Corr bottom_move = move(cur_pos, 1);
        bottom_move.level = cur_level + 1;
        if (valid_step(bottom_move, valid, w - 1, h - 1, 0, 0)){
            S.push(bottom_move);
            possible += 1;
        }
        Corr top_move = move(cur_pos, 0);
        top_move.level = cur_level + 1;
        if (valid_step(top_move, valid, w - 1, h - 1, 0, 0)) {
            S.push(top_move);
            possible += 1;
        }


        Corr right_move = move(cur_pos, 3);
        right_move.level = cur_level + 1;
        if (valid_step(right_move, valid, w - 1, h - 1, 0, 0)) {
            S.push(right_move);
            possible += 1;
        }

        Corr left_move = move(cur_pos, 2);
        left_move.level = cur_level + 1;
        if (valid_step(left_move, valid, w - 1, h - 1, 0, 0)) {
            S.push(left_move);
            possible += 1;
        }
        // 走投无路，当前状态出栈。
        if(possible == 0){
            S.pop();
        }
    }
    int cur_level = S.top().level;
    R.push(S.top());
    S.pop();
    while(!S.empty()){
        if(S.top().level == cur_level){
            S.pop();   //同一层只有可能输出一个节点，根据记录的父节点出栈。
        }
        else{    //要输出的位置。
            R.push(S.top());
            cur_level = S.top().level;
            S.pop();
        }
    }
    while(!R.empty()){   //输出。
        cout<<'('<<R.top().y<<','<<R.top().x<<')'<<endl;
        R.pop();
    }
    
}
// 64 位输出请用 printf("%lld")