已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。 如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。 现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。 求恰好K次移动到棋盘之外的概率 参考：https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/ma-zai-qi-pan-shang-de-gai-lu-by-leetcode/
public class Chessboard { static double[][][] dp; /** * * @param N NxN 的国际象棋棋盘,最左下角的格子记为 (0, 0)，最右上角的记为 (N-1, N-1) * @param K 进行 K 次移动 * @param R,C 初始位于 (R, C) */ public static double knightProbability(int N, int K, int R, int C){ /** * 如果不移动（位于棋盘上） * */ if(K == 0) { return 0; } dp = new double[N][N][K + 1]; return dfs(N, K, R, C); } public static double dfs(int N, int K, int r, int c) { /** * 已经计算过该种情况，直接返回，避免重复 * */ if(dp[r][c][K] > 0) { return dp[r][c][K]; } // 如果是最后一次跳跃 直接执行kis函数 if(K == 1) { return kis(N, r, c); } else { /** * 递归计算八中方向在盘外的概率 * 如果下一次没有出界那么继续递归 */ double res = 0.0d; if(r + 2 < N && c + 1 < N) { res = res + dfs(N, K - 1, r + 2, c + 1); }else{ res ++; } if(r + 2 < N && c - 1 >= 0) { res = res + dfs(N, K - 1, r + 2, c - 1); }else{ res ++; } if(r - 2 >= 0 && c + 1 < N) { res = res + dfs(N, K - 1, r - 2, c + 1); }else{ res ++; } if(r - 2 >= 0 && c - 1 >= 0) { res = res + dfs(N, K - 1, r - 2, c - 1); }else{ res ++; } if(c + 2 < N && r + 1 < N) { res = res + dfs(N, K - 1, r + 1, c + 2); }else{ res ++; } if(c + 2 < N && r - 1 >= 0) { res = res + dfs(N, K - 1, r - 1, c + 2); }else{ res ++; } if(c - 2 >= 0 && r + 1 < N) { res = res + dfs(N, K - 1, r + 1, c - 2); }else{ res ++; } if(c - 2 >= 0 && r - 1 >= 0) { res = res + dfs(N, K - 1, r - 1, c - 2); }else{ res ++; } dp[r][c][K] = res / 8.0d; return dp[r][c][K]; } } /** * 走一步时落在界外的概率 */ private static double kis(int N, int r, int c) { int count = 0; if(r + 2 >= N || c + 1 >= N) { count++; } if(r + 2 >= N || c - 1 < 0) { count++; } if(r - 2 < 0 || c + 1 >= N) { count++; } if(r - 2 < 0 || c - 1 < 0) { count++; } if(c + 2 >= N || r + 1 >= N) { count++; } if(c + 2 >= N || r - 1 < 0) { count++; } if(c - 2 < 0 || r + 1 >= N) { count++; } if(c - 2 < 0 || r - 1 < 0) { count++; } return ((double)count) / 8.0d; } public static void main(String[] args) { /** * 测试用例1 * 返回结果：0.7741116434335709 * */ System.out.println(knightProbability(10,10,4,4)); /** * 测试用例2 * 返回结果：0.0 * */ System.out.println(knightProbability(3,0,0,0)); /** * 测试用例2 * 返回结果：0.9375 * */ System.out.println(knightProbability(3,2,0,0)); } }