Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
已知棋盘格边长和knight的位置(row, column),问k步之后knight仍然在棋盘格上的概率,DFS+
lru_cache


 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 = [[12], [21], [1-2], [2-1], [-12], [-21], [-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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理