1 #688
2 #Runtime: 225 ms (Beats 75.30%)
3 #Memory: 26.5 MB (Beats 13.8%)
4
5 class Solution:
6 def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
7 d = [[1, 2], [2, 1], [1, -2], [2, -1], [-1, 2], [-2, 1], [-1, -2], [-2, -1]]
8
9 @lru_cache(None)
10 def dfs(x, y, k):
11 if k == 0:
12 return 1
13 ans = 0
14 for dx, dy in d:
15 tx = x + dx
16 ty = y + dy
17 if 0 <= tx < n and 0 <= ty < n:
18 ans += dfs(tx, ty, k - 1)
19 return ans
20 if not k:
21 return 1
22 return dfs(row, column, k) / 8**k