题解 | #迷宫问题#

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

int row, col;
vector<vector<int>> maze;
vector<vector<int>> path_tmp;
vector<vector<int>> path_best;

void mazeTrack(int i, int j) {
    maze[i][j] = 1; //代表点(i,j)已经走过
    path_tmp.push_back({i, j});
    //判断是否到达出口
    if (i == row - 1 && j == col - 1) {
	    //寻找最短路径
        if (path_best.empty() || path_best.size() > path_tmp.size())
            path_best = path_tmp;
    }
    //向右走
    if (j + 1 < col && maze[i][j + 1] == 0)
        mazeTrack(i, j + 1);
    //向左走
    if (j - 1 >= 0 && maze[i][j - 1] == 0)
        mazeTrack(i, j - 1);
    //向上走
    if (i - 1 >= 0 && maze[i - 1][j] == 0)
        mazeTrack(i - 1, j);
    //向下走
    if (i + 1 < row && maze[i + 1][j] == 0)
        mazeTrack(i + 1, j);
    maze[i][j] = 0;      //回溯；恢复路径
    path_tmp.pop_back();
}

int main() {
    while (cin >> row >> col) {
        maze = vector<vector<int>> (row, vector<int>(col, 0));
        path_tmp.clear();
        path_best.clear();
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
                cin >> maze[i][j];
        mazeTrack(0, 0);
	  //输出路径
        for(int i=0;i<path_best.size();++i)
        {
            cout<<"("<<path_best[i][0]<<","<<path_best[i][1]<<")"<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")