题解 | #迷宫问题#

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

#define CIN_ARGC 1

#ifdef CIN_ARGC
int row = 0;
int col = 0;
vector<pair<int, int>> vecPairs;
vector<pair<int, int>> vecPairTemp;
vector<vector<int>>  vec2In;
#else
int row = 5;
int col = 5;
vector<pair<int, int>> vecPairs;
vector<pair<int, int>> vecPairTemp;
vector<vector<int>>  vec2In = {
        {0, 1, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0}
    };
#endif
/*
* DFS
* 思路：采用递归原理，输出条件为到达边界点,即横坐标与纵坐标的边界点（row-1, col-1）,左右上下进行递归
* 步骤：
* 第一步：输入二维数组
* 第二步：阻塞节点vec2In[i][j]=1
  第三步：DFS递归，当横坐标的边界点i ==row-1与纵坐标的边界点 j ==col-1, 则输出节点；
*       当i-1>=0 && vec2In[i-1][j]==0，则左递归DFS(i-1, j)；
        当i+1<=row-1 && vec2In[i+1][j]==0，则右递归DFS(i+1, j);
        当j-1>=0 && vec2In[i][j-1]==0，则上递归DFS(i, j-1)
        当j+1<=col-1 && vec2In[i][j+1]==0，则下递归DFS(i, j+1)
* 第四步：非阻塞节点vec2In[i][j]=0
* 第三步：输出节点的坐标
*/
void DFS(int i, int j)
{
    vecPairTemp.push_back({i, j});
    vec2In[i][j] = 1; //已走过
    // 输出条件
    if(i == row - 1 && j == col - 1) {
        vecPairs = vecPairTemp; // 输出节点
        return;
    }
    //左递归
    if(i-1 >= 0 && vec2In[i-1][j] == 0) {
        DFS(i-1, j);
    }    
    //右递归
    if((i+1 <= row-1) && vec2In[i+1][j] == 0) {
        DFS(i+1, j);
    }   
    //上递归
    if(j-1 >= 0 && vec2In[i][j-1] == 0) {
        DFS(i, j-1);
    }  
    //下递归
    if((j+1 <= col-1) && vec2In[i][j+1] == 0) {
        DFS(i, j+1);
    }  
    vec2In[i][j] = 0; //恢复现场
    vecPairTemp.pop_back();

}

int main(int argc, char* argv[])
{

#ifdef CIN_ARGC    
    while(cin >> row >> col) {
        for(int i = 0; i < row; i++) {
            vector<int> vecIn;
            for(int j = 0; j < col; j++) {
                int a = 0;
                cin>>a;
                vecIn.push_back(a);
            }
            vec2In.push_back(vecIn);
        }
        DFS(0, 0);
        for(auto vecPair : vecPairs) {
            cout << "(" << vecPair.first << "," << vecPair.second << ")" << endl;
        }
        vecPairs.clear();
        vecPairTemp.clear();
        vec2In.clear();
   }
#else
    DFS(0, 0);
    for(auto vecPair : vecPairs) {
        cout << "(" << vecPair.first << "," << vecPair.second << ")" << endl;
    }
    vecPairs.clear();
    vecPairTemp.clear();
    vec2In.clear();
#endif
    return 0;
}