688.马-在棋盘上的概率.md

688.马-在棋盘上的概率

/*
 * @lc app=leetcode.cn id=688 lang=typescript
 *
 * [688] “马”在棋盘上的概率
 */

// @lc code=start
function knightProbability(n: number, k: number, row: number, column: number): number {}
// @lc code=end

解法 1: DFS

function knightProbability(n: number, k: number, row: number, column: number): number {
  const dirs = [
    [-1, -2],
    [-2, -1],
    [-2, 1],
    [-1, 2],
    [1, 2],
    [2, 1],
    [2, -1],
    [1, -2],
  ]
  const cache: number[][][] = Array.from({ length: n }, () => Array.from({ length: n }, () => []))
  const dfs = (x: number, y: number, k: number) => {
    if (k === 0) {
      return 1
    }
    if (cache[x][y][k] !== undefined) return cache[x][y][k]
    let res = 0
    for (let [dx, dy] of dirs) {
      const nx = dx + x,
        ny = dy + y
      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
      res += (1 / 8) * dfs(nx, ny, k - 1)
    }
    cache[x][y][k] = res
    return res
  }
  return dfs(row, column, k)
}

解法 2: 动态规划

function knightProbability(n: number, k: number, row: number, column: number): number {
  const dirs = [
    [-1, -2],
    [-2, -1],
    [-2, 1],
    [-1, 2],
    [1, 2],
    [2, 1],
    [2, -1],
    [1, -2],
  ]
  let dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(1))

  for (let i = 0; i < k; i++) {
    const tmp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0))
    for (let x = 0; x < n; x++) {
      for (let y = 0; y < n; y++) {
        for (const [dx, dy] of dirs) {
          const [nx, ny] = [dx + x, dy + y]
          if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
          tmp[x][y] += (1 / 8) * dp[nx][ny]
        }
      }
    }
    dp = tmp
  }
  return dp[row][column]
}

Case

test.each([
  { input: { n: 3, k: 2, row: 0, column: 0 }, output: 0.0625 },
  { input: { n: 1, k: 0, row: 0, column: 0 }, output: 1.0 },
])(
  'input: n = $input.n, k = $input.k, row = $input.row, column = $input.column',
  ({ input: { n, k, row, column }, output }) => {
    expect(knightProbability(n, k, row, column)).toEqual(output)
  },
)