题解 | #迷宫问题#

#include <iostream>
#include <vector>
using namespace std;
int M,N;//行列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_best;//迷宫矩阵
vector<vector<int>> path_temp;//中间矩阵
void bestpath(int i,int j)
{
    //每次走过的点标1
    maze[i][j]=1;
    path_temp.push_back({i,j});//当前节点push进

    //找到最优路径，需要比较，判断结束位置
    if(i==N-1 && j==M-1)//结束
    {
        if(path_temp.size()<path_best.size()||path_best.empty())//比较temp <best或者为空
            path_best=path_temp;
    }
    //走路  回溯
    //上
    if(i-1>=0&&maze[i-1][j]==0)
        bestpath(i-1,j);
    //下
    if(i+1<=N-1&& maze[i+1][j]==0)
        bestpath(i+1,j);
    //左
     if(j-1>=0 && maze[i][j-1]==0 )
        bestpath(i,j-1);
    //右
      if( j+1<=M-1 && maze[i][j+1]==0)
          bestpath(i, j+1);
    //恢复现场
    maze[i][j]=0;

    path_temp.pop_back();
}

int main()
{
    while(cin>>N>>M)
    {
        maze=vector<vector<int>>(N,vector<int>(M,0));
        path_best.clear();
        path_temp.clear();
        //输入迷宫
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M; j++)
            {
                cin>>maze[i][j];
            }
        }

        //回溯法找路径
        bestpath(0, 0);
        for(auto x:path_best)
            cout<<'('<<x[0]<<','<<x[1]<<')'<<endl;
    }
    return 0;
}