题目描述

样例

Example:

输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。

算法

(DFS+memo) O(k∗N^2)

Acwing 1116题目马走日思路，只不过为了避免重复搜索，需要多加一个memo三维数组，表示从[r,c]为原点走K步(每次走日字),能不出界概率。

Java 代码

public class Solution {

    double memo[][][] = null;
    int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
    int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

    public double knightProbability(int N, int K, int r, int c) {
        // 从[r,c]为原点走K步(每次走日字)的不出界概率
        memo = new double[26][26][101];
        return dfs(N, r, c, K);
    }

    private double dfs(int N, int r, int c, int K) {
        if (r >= N || r < 0 || c >= N || c < 0) {
            return 0.0;
        }

        if (memo[r][c][K] != 0.0) {
            return memo[r][c][K];
        }

        if (K == 0) {
            return 1.0;
        }


        double res = 0.0;
        for (int i = 0; i < 8; i++) {
            int x = r + dx[i];
            int y = c + dy[i];
            res += 0.125 * dfs(N, x, y, K - 1);
        }
        memo[r][c][K] = res;
        return res;
    }

}