【Day 59 】2024-06-05 - 688. “马”在棋盘上的概率

[azl397985856]

688. “马”在棋盘上的概率

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/knight-probability-in-chessboard/

前置知识

• 动态规划
• 数组

  题目描述

  
  已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。 

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

[lxy1108]

python3代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        def check(x,y):
            if x>=0 and x<n and y>=0 and y<n:
                return True
            else:
                return False
        @lru_cache
        def step(x,y):
            rs = []
            if check(x-2,y-1):
                rs.append((x-2,y-1))
            if check(x-1,y-2):
                rs.append((x-1,y-2))
            if check(x+1,y-2):
                rs.append((x+1,y-2))
            if check(x+2,y-1):
                rs.append((x+2,y-1))
            if check(x+2,y+1):
                rs.append((x+2,y+1))
            if check(x+1,y+2):
                rs.append((x+1,y+2))
            if check(x-2,y+1):
                rs.append((x-2,y+1))
            if check(x-1,y+2):
                rs.append((x-1,y+2))
            return rs
        queue = collections.defaultdict(int)
        queue[(row, column)] = 1
        for i in range(k):
            # print(queue)
            if not queue:
                return 0
            tmp = collections.defaultdict(int)
            for (x,y),nums in queue.items():
                next_list = step(x,y)
                for nl in next_list:
                    tmp[nl]+=nums
            queue = tmp
        return sum(list(queue.values()))/8**k

[hillsonziqiu]

思路

跟昨天的思路一样，动态窗口；

代码

/*
 * @lc app=leetcode.cn id=688 lang=javascript
 *
 * [688] 骑士在棋盘上的概率
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
const pos = [
  [-2, -1],
  [-2, 1],
  [2, -1],
  [2, 1],
  [-1, -2],
  [-1, 2],
  [1, -2],
  [1, 2],
];
var knightProbability = function (n, k, row, column) {
  const dp = new Array(k + 1)
    .fill(0)
    .map(() => new Array(n).fill(0).map(() => new Array(n).fill(0)));

  for (let step = 0; step <= k; step++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (step === 0) {
          dp[step][i][j] = 1;
        } else {
          for (let [dx, dy] of pos) {
            const x = i + dx;
            const y = j + dy;
            if (x >= 0 && x < n && y >= 0 && y < n) {
              dp[step][i][j] += dp[step - 1][x][y] / 8;
            }
          }
        }
      }
    }
  }

  return dp[k][row][column];
};
// @lc code=end

复杂度分析

• 时间复杂度：O(k*n^2);
• 空间复杂度：O(k*n^2);

[Lizhao-Liu]

func knightProbability(_ n: Int, _ k: Int, _ row: Int, _ column: Int) -> Double {
    let directions = [(-2, -1), (-1, -2), (1, -2), (2, -1),
                      (2, 1), (1, 2), (-1, 2), (-2, 1)]

    var dpPrev = Array(repeating: Array(repeating: 0.0, count: n), count: n)
    var dpCurr = Array(repeating: Array(repeating: 0.0, count: n), count: n)

    dpPrev[row][column] = 1.0

    if k < 1 {
        return 1
    }

    for _ in 1...k {
        for i in 0..<n {
            for j in 0..<n {
                if dpPrev[i][j] > 0 {
                    for direction in directions {
                        let ni = i + direction.0
                        let nj = j + direction.1
                        if ni >= 0 && ni < n && nj >= 0 && nj < n {
                            dpCurr[ni][nj] += dpPrev[i][j] / 8.0
                        }
                    }
                }
            }
        }
        dpPrev = dpCurr
        dpCurr = Array(repeating: Array(repeating: 0.0, count: n), count: n)
    }

    let totalProbability = dpPrev.flatMap { $0 }.reduce(0.0, +)
    return totalProbability
}

[Dtjk]

class Solution { static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

public double knightProbability(int N, int K, int row, int column) {
    double[][][] f = new double[N][N][K + 1];
    for (double[][] x : f)
        for (double[] y : x)
            y[0] = 1;
    for (int step = 1; step <= K; step++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int[] dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    if (x < 0 || x >= N || y < 0 || y >= N) continue;
                    f[i][j][step] += f[x][y][step - 1] / 8;
                }
            }
        }
    }
    return f[row][column][K];
}

}