迷宫问题

描述

迷宫问题_牛客题霸_牛客网
定义一个二维数组 N * M ，如 5 × 5 数组下所示：

maze = {  
  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],既第一格是可以走的路。

数据范围： 2 <= n, m <= 10 ， 输入的内容只包含 0 <= val <= 1  

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的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)

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

解1

思路:
使用 ‘1’ 将整个迷宫包裹起来,表示墙壁。将走过的地方也标记为 ‘1’
开始递归搜索，
分为这几种情况:
碰到墙壁 return []
走到终点 return [终点]
走到走过的路径 return []

正在搜索路径的时候可能的走法
向上、向下、向左、向右
如果返回值不会 [] 则说明找到了路径，直接将当前点加入到路径返回即可。
代码如下:

// 获取输入
const [m, n] = readline().split(" ").map(Number);

// 建立辅助数组
const ast = new Array(m + 2);
for (let i = 0; i < m + 2; i++) {
  if (i === 0) ast[i] = new Array(n + 2).fill(1);
  if (i > 0 && i < m + 1) {
    ast[i] = readline().split(" ").map(Number);
    ast[i].push(1);
    ast[i].unshift(1);
  }
  if (i === m + 1) ast[i] = new Array(n + 2).fill(1);
}

function findPath(ast, i, j) {
  // 到达终点，直接返回
  if (i === m && j === n) return [[i - 1, j -1]];

  // 对于走过的点 置为 1
  ast[i][j] = 1; 
  if (ast[i - 1][j] === 0) {
    const up = findPath(ast, i - 1, j);
    if(up.length) return [[i - 1, j - 1],...up]
  }
  if (ast[i + 1][j] === 0) {
    const down = findPath(ast, i + 1, j);
    if(down.length) return [[i - 1, j - 1],...down] 
  }
  if (ast[i][j - 1] === 0) {
    const left = findPath(ast, i, j - 1);
    if(left.length) return [[i - 1, j - 1],...left]
  }
  if (ast[i][j + 1] === 0) {
    const right = findPath(ast, i, j + 1);
    if(right.length) return [[i - 1, j - 1],...right]
  }
  return [];
}