推 a9486l: 大師 07/22 22:14
→ ILoveErr: 大師 07/22 22:14
推 uiojkl789: 怎麼還沒新增到簽名檔 07/22 22:14
我看看有沒有好看的圖
推 JerryChungYC: 大師 07/22 22:16
※ 編輯: Rushia (122.100.75.86 臺灣), 07/22/2023 22:20:38
推 Che31128: 大師 07/22 22:22
https://leetcode.com/problems/knight-probability-in-chessboard/description/
688. Knight Probability in Chessboard
給你一個數字 n 表示一個 n x n 的西洋棋盤，他的座標用 0-index 來表示
我們把一個騎士放在棋盤的 [row, column] 位置，騎士可以往八個方向移動
https://assets.leetcode.com/uploads/2018/10/12/knight.png
棋子在移動 k 步時停下（可以走出棋盤外），求出騎士恰好移動 k 步之後，他仍留
在棋盤上的機率是多少。
Example 1:
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.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000
方法一：DFS（TLE）
1.一個棋子可以走 k 步，每次有八種走法，所以共有 8^k 種走法，我們只要求出
哪些走法可以停在棋盤上並放在分子即可。
2.用DFS模擬棋子的所有走法，當恰好走完 k 步時沒越界， res 遞增。
3.答案為 res / 所有走法。
Java Code：
-----------------------------------------------
class Solution {
private int res;
public double knightProbability(int n, int k, int row, int column) {
res = 0;
dfs(n, k, row, column);
return res / Math.pow(8, k);
}
private int[][] dirs = {{2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2,
-1}, {1, -2}, {-1, -2}};
private void dfs(int n, int k, int r, int c) {
if (r >= n || r < 0 || c >= n || c < 0) {
return;
}
if (k == 0) {
res++;
return;
}
for (int[] dir : dirs) {
dfs(n, k - 1, r + dir[0], c + dir[1]);
}
}
}
-----------------------------------------------
方法二：DFS + DP
1.因為在遞迴的過程中存在許多重複計算，一個點可以從八個座標訪問，
而那八個座標也可以被另外八個座標訪問所以導致棋盤大小太大時會超時。
2.利用一個三維陣列 memo[r][c][k] 暫存已經算過的結果，memo[r][c][k]
表示在座標 [r,c] 時，還有 k 步可以走的合法棋子數量，如果有值直接返回。
3.其他就跟上面一樣。
Java Code：
---------------------------------------------------------
class Solution {
private double[][][] memo;
public double knightProbability(int n, int k, int row, int column) {
memo = new double[n][n][k + 1];
double res = dfs(n, k, row, column);
return res / Math.pow(8, k);
}
private int[][] dirs = {{2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2,
-1}, {1, -2}, {-1, -2}};
private double dfs(int n, int k, int r, int c) {
if (r >= n || r < 0 || c >= n || c < 0) {
return 0;
}
if (memo[r][c][k] != 0) {
return memo[r][c][k];
}
if (k == 0) {
return 1;
}
for (int[] dir : dirs) {
memo[r][c][k] += dfs(n, k - 1, r + dir[0], c + dir[1]);
}
return memo[r][c][k];
}
}
---------------------------------------------------------
https://i.imgur.com/LwkaAda.jpg
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690035200.A.9B8.html