688. “马”在棋盘上的概率

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.Arrays;

class Solution {

    private static final int[][] directions = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
            {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

    public double knightProbability(int n, int steps, int row, int column) {
        double[][] dp = new double[n][n];
        dp[row][column] = 1;
        while (steps-- > 0) {
            double[][] helper = new double[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    for (int k = 0; k < directions.length; ++k) {
                        int x = i + directions[k][0];
                        int y = j + directions[k][1];
                        if (x >= 0 && x < n && y >= 0 && y < n) {
                            helper[x][y] += dp[i][j] / 8.0;
                        }
                    }
                }
            }
            dp = helper;
        }
        double ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ans += dp[i][j];
            }
        }
        return ans;
    }
}