介绍

一个迷宫是由 N*N 个区块组成的二进制矩阵，其中源区块是最左上方的区块，即 maze[0][0] ，目的地区块是最右下方的区块，即 maze[N-1][N-1] 。一只老鼠从源头开始，必须到达目的地。大鼠只能在两个方向移动：向前和向下。

在迷宫矩阵中，0 表示该区块是一个死胡同，1 表示该区块可以用于从源头到目的地的路径中。请注意，这是典型迷宫问题的一个简单版本。例如，更复杂的版本可以是老鼠可以在 4 个方向移动，更复杂的版本可以是有限制的移动次数。

回溯算法：回溯是一种算法技术，通过尝试逐步建立一个解决方案来递归地解决问题。一次解决一个问题，并删除那些在任何时间点上不能满足问题约束的解决方案（这里的时间是指到达搜索树的任何一级所花费的时间），这就是回溯的过程。

方法：形成一个递归函数，它将遵循一个路径并检查该路径是否到达目的地。如果该路径没有到达目的地，则回溯并尝试其他路径。

实现

JavaScript

/*
 * Problem Statement:
 * - Given a NxN grid, find whether rat in cell [0, 0] can reach the target in cell [N-1, N-1]
 * - The grid is represented as an array of rows. Each row is represented as an array of 0 or 1 values.
 * - A cell with value 0 can not be moved through. Value 1 means the rat can move here.
 * - The rat can not move diagonally（对角地）.
 *
 * Reference for this problem: https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/
 *
 * Based on the original implementation contributed by Chiranjeev Thapliyal (https://github.com/chiranjeev-thapliyal).
 */

/**
 * Checks if the given grid is valid.
 *
 * A grid needs to satisfy these conditions:
 * - must not be empty
 * - must be a square
 * - must not contain values other than {@code 0} and {@code 1}
 *
 * @param grid The grid to check.
 * @throws TypeError When the given grid is invalid.
 */
function validateGrid (grid) {
  if (!Array.isArray(grid) || grid.length === 0) throw new TypeError('Grid must be a non-empty array')

  const allRowsHaveCorrectLength = grid.every(row => row.length === grid.length)
  if (!allRowsHaveCorrectLength) throw new TypeError('Grid must be a square')

  const allCellsHaveValidValues = grid.every(row => {
    return row.every(cell => cell === 0 || cell === 1)
  })
  if (!allCellsHaveValidValues) throw new TypeError('Grid must only contain 0s and 1s')
}

function isSafe (grid, x, y) {
  const n = grid.length
  return x >= 0 && x < n && y >= 0 && y < n && grid[y][x] === 1
}

/**
 * Attempts to calculate the remaining path to the target.
 *
 * @param grid The full grid.
 * @param x The current X coordinate.
 * @param y The current Y coordinate.
 * @param solution The current solution matrix.
 * @param path The path we took to get from the source cell to the current location.
 * @returns {string|boolean} Either the path to the target cell or false.
 */
function getPathPart (grid, x, y, solution, path) {
  const n = grid.length

  // are we there yet?
  if (x === n - 1 && y === n - 1 && grid[y][x] === 1) {
    solution[y][x] = 1
    return path
  }

  // did we step on a 0 cell or outside the grid?
  if (!isSafe(grid, x, y)) return false

  // are we walking onto an already-marked solution coordinate?
  if (solution[y][x] === 1) return false

  // none of the above? let's dig deeper!

  // mark the current coordinates on the solution matrix
  solution[y][x] = 1

  // attempt to move right
  const right = getPathPart(grid, x + 1, y, solution, path + 'R')
  if (right) return right

  // right didn't work: attempt to move down
  const down = getPathPart(grid, x, y + 1, solution, path + 'D')
  if (down) return down

  // down didn't work: attempt to move up
  const up = getPathPart(grid, x, y - 1, solution, path + 'U')
  if (up) return up

  // up didn't work: attempt to move left
  const left = getPathPart(grid, x - 1, y, solution, path + 'L')
  if (left) return left

  // no direction was successful: remove this cell from the solution matrix and backtrack
  solution[y][x] = 0
  return false
}

function getPath (grid) {
  // grid dimensions
  const n = grid.length

  // prepare solution matrix
  const solution = []
  for (let i = 0; i < n; i++) {
    const row = Array(n)
    row.fill(0)
    solution[i] = row
  }

  return getPathPart(grid, 0, 0, solution, '')
}

/**
 * Creates an instance of the "rat in a maze" based on a given grid (maze).
 */
export class RatInAMaze {
  constructor (grid) {
    // first, let's do some error checking on the input
    validateGrid(grid)

    // attempt to solve the maze now - all public methods only query the result state later
    const solution = getPath(grid)

    if (solution !== false) {
      this.path = solution
      this.solved = true
    } else {
      this.path = ''
      this.solved = false
    }
  }
}

扩展

给定一个有障碍物的迷宫，计算从最上面的最下面的单元格到达最右边的最下面的单元格的路径数量。在给定的迷宫中，如果一个单元格是障碍物或死胡同，其值为 - 1，否则为 0。

从一个给定的单元格，我们只允许移动到单元格（i+1，j）和（i，j+1）。

Input: maze[R][C] =  {{0,  0, 0, 0},
                      {0, -1, 0, 0},
                      {-1, 0, 0, 0},
                      {0,  0, 0, 0}};
Output: 4
There are four possible paths.

我们的想法是修改给定的 grid[][] ，使 grid[i][j] 包含从 （0，0） 到达 （i，j） 的路径数，如果 （i，j） 不是障碍物，否则 grid[i][j] 仍然是 - 1。

// JavaScript program to count number of paths in a maze with obstacles.
// R C means maze[R][C]
let R = 4;
let C = 4;
   
// Returns count of possible paths in
// a maze[R][C] from (0,0) to (R-1,C-1)
function countPaths(maze){
  // If the initial cell is blocked, there is no way of moving anywhere
  if (maze[0][0] == -1) return 0;
 
  // Initializing the leftmost column
  for(let i = 0; i < R; i++) {
    if (maze[i][0] == 0) maze[i][0] = 1;
    // If we encounter a blocked cell in leftmost row, there is no way of visiting any cell directly below it.
    else break;
  }
 
  // Similarly initialize the topmost row
  for(let i = 1; i < C; i++) {
    if (maze[0][i] == 0) maze[0][i] = 1;
    // If we encounter a blocked cell in bottommost row, there is no way of visiting any cell directly below it.
    else break;
  }
 
  // The only difference is that if a cell is -1, simply ignore it else recursively compute count value maze[i][j]
  for(let i = 1; i < R; i++) {
    for(let j = 1; j < C; j++) {
      // If blockage is found, ignore this cell
      if (maze[i][j] == -1) continue;
      // If we can reach maze[i][j] from maze[i-1][j] then increment count.
      if (maze[i - 1][j] > 0) maze[i][j] = (maze[i][j] + maze[i - 1][j]);
      // If we can reach maze[i][j] from maze[i][j-1] then increment count.
      if (maze[i][j - 1] > 0) maze[i][j] = (maze[i][j] + maze[i][j - 1]);
    }
  }
 
  // If the final cell is blocked, output 0, otherwise the answer
  return (maze[R - 1][C - 1] > 0) ? maze[R - 1][C - 1] : 0;
}

时间复杂度：O (R x C) 辅助空间：O (1)

参考

• Rat in a Maze | Backtracking-2 - GeeksforGeeks (opens new window)
• Count number of ways to reach destination in a Maze - GeeksforGeeks (opens new window)