Сложность: medium
На шахматной доске размером 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.
👨💻 Алгоритм:
1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня.
2⃣Итерация по ходам от 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].
3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность.
😎 Решение:
class Solution {
function knightProbability($n, $k, $row, $column) {
$directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]];
$dp = array_fill(0, $k + 1, array_fill(0, $n, array_fill(0, $n, 0)));
$dp[0][$row][$column] = 1;
for ($moves = 1; $moves <= $k; $moves++) {
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
foreach ($directions as $direction) {
$prevI = $i - $direction[0];
$prevJ = $j - $direction[1];
if ($prevI >= 0 && $prevI < $n && $prevJ >= 0 && $prevJ < $n) {
$dp[$moves][$i][$j] += $dp[$moves - 1][$prevI][$prevJ] / 8;
}
}
}
}
}
$totalProbability = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
$totalProbability += $dp[$k][$i][$j];
}
}
return $totalProbability;
}
}Ставь 👍 и забирай 📚 Базу знаний