688.骑士在棋盘上的概率

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

题解 1 - 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;
   }
};