490.the-maze.md

由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。

给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。

迷宫由一个 0 和 1 的二维数组表示。 1 表示墙壁，0 表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

示例 1:

输入 1: 迷宫由以下二维数组表示

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)

输出: true

解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

---

1. 遇到墙的位置记录停留坐标
2. 停留坐标记录为 2
3. 如果到达了已经到达的位置，返回 false
4. 到达了目标位置返回 true

var hasPath = function (maze, start, destination) {
  maze.unshift(new Array(maze[0].length + 2).fill(1));
  maze.push(new Array(maze[0].length + 2).fill(1));
  for (let i = 1; i < maze.length - 1; i++) {
    maze[i].unshift(1);
    maze[i].push(1);
  }
  start = [start[0] + 1, start[1] + 1];
  destination = [destination[0] + 1, destination[1] + 1];
  let dirR = [-1, 0, 1, 0];
  let dirC = [0, 1, 0, -1];
  // 是否到达目标位置
  function dfs(i, j) {
    if (maze[i][j] == 2) return false;
    maze[i][j] = 2;
    if (i == destination[0] && j == destination[1]) return true;

    let flag = false;
    for (let d = 0; d < 4; d++) {
      let r = dirR[d] + i;
      let c = dirC[d] + j;
      while (maze[r][c] != 1) {
        r += dirR[d];
        c += dirC[d];
      }
      r -= dirR[d];
      c -= dirC[d];
      flag = flag || dfs(r, c);
    }
    return flag;
  }
  return dfs(start[0], start[1]);
};