980-不同路径III.md

题目描述

不同路径 III

题目简述

在二维网格 grid 上，有 4 种类型的方格：

• 1 表示起始方格。且只有一个起始方格。
• 2 表示结束方格，且只有一个结束方格。
• 0 表示我们可以走过的空方格。
• -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例1

• 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
• 输出：2
• 解释：我们有以下两条路径：

1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

分类

困难 矩阵 回溯

思路

思路1

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function(grid) {
  let zeroLeft = grid.flat().filter(i => i === 0).length
  let wayNum = 0
  function backTrack (point) {
    if (grid[point[0]][point[1]] === 2) {
      if (zeroLeft === 0) {
        wayNum ++
      }
      return
    }
    // 选择
    const ways = judgePosition(...point).filter(i => i[2] === 0 || i[2] === 2).sort((x, y) => x[2] - y[2])
    for(let i = 0; i< ways.length; i++) {
      if (grid[ways[i][0]][ways[i][1]] === 0) {
        grid[ways[i][0]][ways[i][1]] = -2
        zeroLeft--
      }
      backTrack(ways[i].slice(0, 2))
      if (grid[ways[i][0]][ways[i][1]] === -2) {
        grid[ways[i][0]][ways[i][1]] = 0
        zeroLeft++
      }
    }
  }
  /**
   * 
   * @param {*} x 
   * @param {*} y 
   * @returns 左 右 下 上
   */
  function judgePosition (x, y) {
    return [
      [x - 1, y, grid[x - 1] ? grid[x - 1][y] : undefined],
      [x + 1, y, grid[x + 1] ? grid[x + 1][y] : undefined],
      [x, y + 1, grid[x][y + 1]],
      [x, y - 1, grid[x][y - 1]]]
  }
  for (let row = 0; row < grid.length; row ++) {
    const _index = grid[row].findIndex(i => i === 1)
    if (_index !== -1) {
      backTrack([row, _index])
      break
    }
  }
  return wayNum
};

• 问题拆解
  • 阅读题目后，很明显能够使用回溯去解决，我们不难发现四种方格中，-1对我们来说是一个限制条件，起点1和终点2是已知、唯一的，只有0是我们的“变数”。
  • 因为我们需要通过所有的0，这也是我们回溯的终止条件之一，所以先声明zeroLeft用于储存还剩余多少个没有通过的0。再声明wayNum用于储存已经找到的路径数量，也就是最终需要返回的结果。
  • 很容易找到回溯的终止条件，当前网格的值为终点2，而且zeroLeft === 0。
  • 接下来确定单次回溯的所有可能的规则，也就是基于当前点位的下一步的选择。
    • 下一步的寻找由函数judgePosition处理，就是找到当前点位的上下左右，返回四个元素的数组，每个元素包含点位的位置(x, y)以及类型(-1 | 0 | 1 | 2 | undefined)。如果数组位置越界了，则类型为undefined
    • 对judgePosition返回的数组进行筛选，只需要类型为0或者2的
    • 因为可能存在一个0被多次查找到的情况，所以每次经过0后，把0置为-2，也就是把-2作为经过的0的标识。如果回退就再把-2置为0即可。经过0也同时对zeroLeft做增减操作。