Skip to main content

688. Knight Probability in Chessboard

https://leetcode.com/problems/knight-probability-in-chessboard/

Python​

DFS with cache​

from functools import cache


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        if k == 0:
            return 1

        alts = [(2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1)]

        @cache
        def dfs(x, y, remain):
            if remain <= 0:
                return 1

            ans=0
            for dx, dy in alts:
                nx = x + dx
                ny = y + dy
                if 0 <= nx <= n-1 and 0 <= ny <= n-1:
                    ans += dfs(nx, ny, remain-1)

            return ans

        return dfs(row,column,k) / 8**k