688.骑士在棋盘上的概率

链接：688.骑士在棋盘上的概率
难度：Medium
标签：动态规划
简介：返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

题解 1 - python

• 编辑时间：2024-12-07
• 内存消耗：17.23MB
• 编程语言：python
• 解法介绍：遍历。

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        CNT = 8
        x = y = 0
        for i in range(CNT):
            for j in range(CNT):
                if board[i][j] == 'R':
                    x = i
                    y = j
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        res = 0
        for dir in dirs:
            cnt = 1
            while True:
                nx = x + dir[0] * cnt
                ny = y + dir[1] * cnt
                if 0 <= nx < CNT and 0 <= ny < CNT:
                    if board[nx][ny] == '.':
                        cnt += 1
                        continue
                    else:
                        if board[nx][ny] == 'p':
                            res += 1
                break
        return res

题解 2 - cpp

• 编辑时间：2022-02-17
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：动态规划，统计每个点的概率。

int dirs[8][2] = {{-1, -2}, {-1, 2}, {-2, -1}, {-2, 1},
          {1, 2},   {1, -2}, {2, 1},   {2, -1}};
class Solution {
  public:
   double knightProbability(int n, int k, int row, int column) {
       double table[2][n][n], ans = 0;
       memset(table, 0, sizeof(double) * 2 * n * n);
       table[0][row][column] = 1;
       for (int i = 0; i < k; i++) {
           int idx = i & 1, nidx = (i + 1) & 1;
           memset(table[nidx], 0, sizeof(double) * n * n);
           for (int row = 0; row < n; row++) {
               for (int col = 0; col < n; col++) {
                   if (table[idx][row][col] == 0) continue;
                   for (int next = 0; next < 8; next++) {
                       int nrow = row + dirs[next][0],
                           ncol = col + dirs[next][1];
                       if (nrow < 0 || nrow >= n || ncol < 0 || ncol >= n)
                           continue;
                       table[nidx][nrow][ncol] +=
                           1.0 / 8 * table[idx][row][col];
                   }
               }
           }
       }
       for (int row = 0; row < n; row++) {
           for (int col = 0; col < n; col++) {
               if (table[k & 1][row][col]) ans += table[k & 1][row][col];
           }
       }
       return ans;
   }
};