688. Knight Probability in Chessboard
На шахматной доске размером 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# решение
сопоставлено/оригинал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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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
}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]. Верните общую вероятность.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.