688. “马”在棋盘上的概率(字节三面)

比眉伴天荒 2022-10-10 01:50 143阅读 0赞

> 已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 
> 
> 现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。 
> 
> 如下图所示，国际象棋的 “马” 每一步先沿**水平或垂直**方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
> 
> ![20210625195929666.png][]
> 
> 现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。
> 
> 求移动结束后，“马” 仍留在棋盘上的概率。

class Solution {
        Double [][][]memo;
    /**
    dfs+备忘录
     */
        public double knightProbability(int n, int k, int row, int column) {
             memo=new Double[n+1][n+1][k+1];   
             return dfs(n,k,row,column);
        }
    
        public double dfs(int n,int k,int i,int j){
            if(i<0||j<0||i>=n||j>=n){
                return 0;
            }
            if(k==0){
                return 1;
            }
            if(memo[i][j][k]!=null){
                return memo[i][j][k];
            }
            double ans=0;
            ans=
            dfs(n,k-1,i-2,j-1)+dfs(n,k-1,i-2,j+1)
            +dfs(n,k-1,i+2,j-1)+dfs(n,k-1,i+2,j+1)
            +dfs(n,k-1,i+1,j-2)+dfs(n,k-1,i-1,j-2)
            +dfs(n,k-1,i+1,j+2)+dfs(n,k-1,i-1,j+2);
    
            memo[i][j][k]=ans/8;
            return ans/8;//还在棋盘上的数目/可以走的8中可能 
        }
    }

[20210625195929666.png]: /images/20221005/39ef38cfc6614036ac134aa85de4d47c.png