迷宫问题
算法知识视频讲解
中等 通过率：33.13% 时间限制：1秒 空间限制：32M
知识点
查找
排序
题目
题解(38)
讨论(295)
排行
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {
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,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一格是可以走的路。

本题含有多组数据。

输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：
左上角到右下角的最短路径，格式如样例所示。

示例1
输入：
5 5
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
复制
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
复制
示例2
输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
复制
输出：

(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

复制
说明：
注意：不能斜着走！！

#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;
}