Leetcode 688 Solution

This article provides solution to leetcode question 688 (knight-probability-in-chessboard)
Categories:
Tags:
Access this page by simply typing in "lcs 688" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        cache = {}

        def dfs(N, K, r, c, prop):
            if K == 0 and (0 <= r < N and 0 <= c < N):
                return prop

            if not (0 <= r < N and 0 <= c < N):
                return 0

            key = (r, c, prop)
            if key in cache:
                return cache[key]

            ans = 0
            for r_delta, c_delta in [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]:
                ans += dfs(N, K - 1, r + r_delta, c + c_delta, prop * 0.125)
            cache[key] = ans
            return ans

        return dfs(N, K, r, c, 1)