题解 | #迷宫问题#

#include<iostream>
#include<vector>

using namespace std;
int m, n;
vector<vector<int>> mi;
vector<vector<int>> now_path;
vector<vector<int>> best_path;

void dfs(int i, int j)
{
    if(i < 0 || i >= n|| j < 0|| j>=m || mi[i][j] == 1)
    {
        return;
    }
    mi[i][j] = 1;
    now_path.push_back({i, j});
    if(i == n-1 && j == m-1)//先填进去在判断，不然会漏掉最后的一个位置
    {
        best_path = now_path;
    }
    
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
    mi[i][j] = 0;
    now_path.pop_back();
}

int main()
{
   
    while(cin>>n>>m)
    {
        mi = vector<vector<int>>(n,vector<int>(m,0));//必须初始化！！！！
        best_path.clear();
        now_path.clear();
        for(int i = 0; i < n;i++)
        {
            for(int j = 0; j < m;j++)
            {
                cin>>mi[i][j];
            }
        }
        dfs(0 ,0);
        for(vector<vector<int>>::iterator it = best_path.begin();it != best_path.end();it++)//写法学一下
        {
            cout<<'('<<(*it)[0]<<','<<(*it)[1]<<')'<<endl;
        }
    }
    return 0;
}