题解 | #迷宫问题#

简洁的递归代码

#include<vector>
using namespace std;

bool Dfs(vector<vector<int>> & arrays,int n,int m,vector<vector<int>> &  Result)
{
    if(n == arrays.size()-1 && m == arrays[0].size()-1)
    {
         Result.push_back({n,m});
         return true;
    }
       
    else
    {
        Result.push_back({n,m});
        arrays[n][m] = 2;
        bool left =false;
        bool right= false;
        bool up = false;
        bool down = false;
        //朝上边
        if(n-1>-1&&arrays[n-1][m] == 0)
            up = Dfs(arrays, n-1, m,Result);
        //朝下边
        if(n+1<arrays.size()&&arrays[n+1][m] == 0)
            down = Dfs(arrays, n+1, m,Result);
        //朝右边
        if(m+1<arrays[0].size()&&arrays[n][m+1] == 0)
            right= Dfs(arrays, n, m+1,Result);
        //朝左边
        if(m-1>-1&&arrays[n][m-1] == 0)
            left = Dfs(arrays, n, m-1,Result);
        if( !(up|down|right|left))
        {
            arrays[n][m] = 0;
            Result.pop_back();
            return false;
        }
        else
            return true;
       
    }
}

int main()
{
    int n ;
    int m;
    cin >>n>>m;
    vector<vector<int>> Arrays(n,vector<int>(m,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int k;
            cin >>k;
            Arrays[i][j] =k; 
        }
    }
    vector<vector<int>> Result;
    Dfs(Arrays,0,0,Result);
    for(int i=0;i<Result.size();i++)
        cout<<"("<<Result[i][0]<<","<<Result[i][1]<<")"<<endl;
}