688. Knight Probability in Chessboard
На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).
Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.
Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда.
Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.
return вероятность того, что конь останется на доске после того, как он завершит свои ходы.
示例:
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++ 解法
自动草稿，提交前请检查#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]. return общую вероятность.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.