knight-probability-in-chessboard (BF)

knight_probability.py

def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
    grid = [[0] * N for _ in range(N)]
    # utility to count number of moves given a starting position
    def recur(r: int, c: int, k: int) -> int:
        if not (0 <= r < N and 0 <= c < N):
            return 0
        if k == 0:
            return 1
        # try all 8 possible moves
        return (
            recur(r - 2, c + 1, k - 1)
            + recur(r - 2, c -1, k - 1)
            + recur(r - 1, c + 2, k - 1)
            + recur(r - 1, c - 2, k - 1)
            + recur(r + 1, c + 2, k - 1)
            + recur(r + 1, c - 2, k - 1)
            + recur(r + 2, c + 1, k - 1)
            + recur(r + 2, c - 1, k - 1)
        )

    return recur(r, c, K) / float(8 ** K)