题解 | #迷宫问题#

---

题目链接

迷宫问题

题目描述

定义一个二维数组 N*M ，如 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)

---

解题思路

简单寻路，注意多组输入即可。使用的方法是dfs，在每一次到达终点时判断是否为更短路并刷新，就OK。

---

题解

while (line = readline()) {let nums = line.split(' ');let col = +nums[0];let row = +nums[1];let map = [];for (let i = 0; i < col; i++) {map.push([]);let mapline = readline().split(' ');for (let j = 0; j < row; j++) {map[i][j] = +mapline[j];}}let minLine = [];let nowLine = [];let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];let book = [];for (let i = 0; i < col; i++) {book.push([]);for (let j = 0; j < row; j++) {book[i][j] = 0;}}let dfs = (x, y) => {nowLine.push(`(${x},${y})`);book[x][y] = 1;if (x == col - 1 && y == row - 1) {if (minLine.length == 0 || nowLine.length < minLine.length) {minLine = [];for (let i = 0; i < nowLine.length; i++) {minLine[i] = nowLine[i];}}book[x][y] = 0;nowLine.pop();return;}for (let i = 0; i < 4; i++) {let tox = x + dir[i][0];let toy = y + dir[i][1];if (tox >= 0 && tox < col && toy >= 0 && toy < row && map[tox][toy] == 0 && book[tox][toy] == 0) {dfs(tox, toy);}}book[x][y] = 0;nowLine.pop();return;}dfs(0, 0);for (let i = 0; i < minLine.length; i++) {console.log(minLine[i]);}
}