题解 | #迷宫问题#

#include<iostream>
#include<vector>
#include<map>
#include<algorithm> 
#include<math.h>
#include<set>
#include<stack>
#include<queue>
#include<memory.h>
using namespace std;

int Map[20][20];//点状态 墙壁或者路径
int pre[20][20];//如何到达当前点

// 移动方式-左右上下
int dx[4] = {0,0,-1,1};
int dy[4] = { -1,1,0,0 };

int main() {
    memset(pre, -1, sizeof pre);//初始化到达方式
    queue<pair<int, int>> points;//遍历到的位置
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> Map[i][j];
        }
    }
    ///输入结束
  
    //从起点开始搜索
    pair<int, int> target = pair<int, int>(n - 1, m - 1);//终点位置
    points.push(pair<int, int>(0, 0));
    while (!points.empty()) {
        bool find = false;
        pair<int, int> p = points.front();
        points.pop();
        for (int i = 0; i < 4; i++) {
            int new_x = p.first + dx[i];
            int new_y = p.second + dy[i];
            
            if (new_x<0 || new_x>n - 1 || new_y<0 || new_y>m - 1||Map[new_x][new_y]==1) continue;//排除走不了的点
            if (pre[new_x][new_y] != -1) continue;//已经遍历过了

            pre[new_x][new_y] = i;//到达方式
            pair<int, int> p_new = pair<int, int>(new_x, new_y);//新到达的点
            if (p_new == target) {//已经到达终点了
                break;
                find = true;
            }
            else {
                points.push(p_new);
            }
        }
        if (find)break;//已经到达终点了
    }
    //使用栈查找来时路径-从终点到起点入栈
    stack< pair<int, int>> solution;
    int p_x = n-1, p_y = m-1;
    solution.push(target);
    while (!(p_x == 0 && p_y == 0)) {
        //更新位置
        int d_x = dx[pre[p_x][p_y]];
        int d_y= dy[pre[p_x][p_y]];
        p_x -= d_x;
        p_y -= d_y;
        //加入点
        solution.push(pair<int, int>(p_x, p_y));
    }
    //使用栈查找来时路径-从起点到终点出栈
    while (!solution.empty()) {
        pair<int, int> p = solution.top();
        solution.pop();
        cout << "(" << p.first << "," << p.second << ")" << endl;
    }
    return 0;
}