Leetcode 688. Knight Probability in Chessboard
📅2023-07-22🧐58
In the first, I try to use BFS, and sooner I figured out we don't need to try every path, just one path will be used for the calculation of the probability in a chessboard. So insteadly I use DFS to solve this problem. And since Knight can go back to a position, we treat the visited position as over lapping subproblems.
from functools import lru_cache
class Solution:
def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
if k <= 0:
return 1.0
dirs = [(-1, -2), (-2, -1), (-1, 2), (-2, 1), (1, -2), (2, -1), (1, 2), (2, 1)]
@lru_cache(None)
def dfs(r, c, k):
if r < 0 or c < 0 or r >= n or c >= n:
return 0
if k == 0:
return 1
on = 0
for x, y in dirs:
nr, nc = r + x, c + y
on += dfs(nr, nc, k - 1)
return on / 8
return dfs(row, column, k)