题解 | #迷宫问题#

#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

stack<pair<int, int>> path;//记录路径

void MazeInput(vector<vector<int>>& maze, int row, int col)//输入迷宫
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> maze[i][j];
        }
    }
}

//DFS寻找路径
bool FindPath(vector<vector<int>>& maze, int row, int col, pair<int, int> pos)
{
    int x = pos.first;
    int y = pos.second;
    path.push(pos);
    if(x < 0 || x >= row || y < 0 || y >= col || maze[x][y] != 0)
    {
        path.pop();
        return false;
    }
    if((x == row - 1) && (y == col - 1))
    {
        return true;
    }

    maze[x][y] = 2;
    bool res = FindPath(maze, row, col, pair<int, int>(x - 1, y)) ||
    FindPath(maze, row, col, pair<int, int>(x + 1, y)) ||
    FindPath(maze, row, col, pair<int, int>(x, y - 1)) ||
    FindPath(maze, row, col, pair<int, int>(x, y + 1));

    if(!res){
        path.pop();
    }
    return res;
}

//打印路径
void PrintPath(stack<pair<int, int>>& pt)
{
    stack<pair<int, int>> rPath;
    while(!pt.empty())
    {
        rPath.push(pt.top());
        pt.pop();
    }
    while(!rPath.empty())
    {
        cout << "(" << rPath.top().first << "," << rPath.top().second << ")" << endl;
        rPath.pop();
    }
}

int main()
{
    int row = 0;
    int col = 0;
    cin >> row >> col;
    vector<vector<int>> maze(row, vector<int>(col, 0));
    MazeInput(maze, row, col);
    pair<int, int> pos(0, 0);
    FindPath(maze, row, col, pos);
    PrintPath(path);
    return 0;
}