← Static tasks

688. Knight Probability in Chessboard

leetcode medium

#array#csharp#dynamic-programming#leetcode#matrix#medium#string

Task

На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).

Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.

Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда.

Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.

Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.

Пример:

Input: n = 3, k = 2, row = 0, column = 0

Output: 0.06250

Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.

From each of those positions, there are also two moves that will keep the knight on the board.

The total probability the knight stays on the board is 0.0625.

C# solution

matched/original
public class Solution {
    public double KnightProbability(int n, int k, int row, int column) {
        int[][] directions = new int[][] {
            new int[] {1, 2}, new int[] {1, -2}, new int[] {-1, 2}, new int[] {-1, -2},
            new int[] {2, 1}, new int[] {2, -1}, new int[] {-2, 1}, new int[] {-2, -1}
        };
        double[][][] dp = new double[k + 1][][];
        for (int i = 0; i <= k; i++) {
            dp[i] = new double[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new double[n];
            }
        }
        dp[0][row][column] = 1;
        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }
        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }
        return totalProbability;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double KnightProbability(int n, int k, int row, int column) {
        int[][] directions = new int[][] {
            new int[] {1, 2}, new int[] {1, -2}, new int[] {-1, 2}, new int[] {-1, -2},
            new int[] {2, 1}, new int[] {2, -1}, new int[] {-2, 1}, new int[] {-2, -1}
        };
        double[][][] dp = new double[k + 1][][];
        for (int i = 0; i <= k; i++) {
            dp[i] = new double[n][];
            for (int j = 0; j < n; j++) {
                dp[i][j] = new double[n];
            }
        }
        dp[0][row][column] = 1;
        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (vector<int>& direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }
        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }
        return totalProbability;
    }
}

Java solution

matched/original
class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        double[][][] dp = new double[k + 1][n][n];
        dp[0][row][column] = 1;

        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }

        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }

        return totalProbability;
    }
}

JavaScript solution

matched/original
class Solution {
    knightProbability(n, k, row, column) {
        const directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]];
        const dp = Array.from({ length: k + 1 }, () => Array.from({ length: n }, () => Array(n).fill(0)));
        dp[0][row][column] = 1;

        for (let moves = 1; moves <= k; moves++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    for (const [dx, dy] of directions) {
                        const prevI = i - dx;
                        const prevJ = j - dy;
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }

        return dp[k].flat().reduce((acc, val) => acc + val, 0);
    }
}

Python solution

matched/original
class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        dp[0][row][column] = 1

        for moves in range(1, k + 1):
            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        prevI, prevJ = i - direction[0], j - direction[1]
                        if 0 <= prevI < n and 0 <= prevJ < n:
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8

        return sum(map(sum, dp[k]))

Go solution

matched/original
package main

func knightProbability(n int, k int, row int, column int) float64 {
    directions := [8][2]int{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}
    dp := make([][][]float64, k+1)
    for i := range dp {
        dp[i] = make([][]float64, n)
        for j := range dp[i] {
            dp[i][j] = make([]float64, n)
        }
    }
    dp[0][row][column] = 1

    for moves := 1; moves <= k; moves++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                for _, direction := range directions {
                    prevI, prevJ := i-direction[0], j-direction[1]
                    if prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n {
                        dp[moves][i][j] += dp[moves-1][prevI][prevJ] / 8
                    }
                }
            }
        }
    }

    totalProbability := 0.0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            totalProbability += dp[k][i][j]
        }
    }

    return totalProbability
}

Explanation

Algorithm

Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.

Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j].

Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.

😎