题解 | #迷宫问题#
迷宫问题
http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
迷宫问题
算法知识视频讲解
中等 通过率: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; }