题解 | #迷宫问题#

#include<iostream>
#include<vector>
using namespace std;
int n,m,f;
vector<vector<int>> maze,path;
void dfs(int i,int j)
{
    //1 不符合 return数组越界or“墙壁”或已走过or已找到
    if(i<0||i>=n||j<0||j>=m||maze[i][j]==1||f)
        return;
    //2 符合 记录
    maze[i][j]=1;
    path.push_back({i,j});
    //3 判断终点
    if(i==n-1&&j==m-1){f=1;return;}
    //4 递归
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
    //5 被return且f==0,走不通
    if(f==0)
    {
        maze[i][j]=0;
        path.pop_back();
    }
}
int main()
{
    while(cin>>n>>m)
    {
        f=0;
        maze=vector<vector<int>>(n,vector<int>(m,0));
        path.clear();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>maze[i][j];
        dfs(0,0);
        for(auto i:path)
            cout<<'('<<i[0]<<','<<i[1]<<')'<<endl;
    }
}