688. Knight Probability in Chessboard

link

Method 1 Backtrack

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        @cache
        def dfs(nn, r, col):
            if not (0 <= r < n and 0 <= col < n):
                return 0

            if nn == k:
                return 1
                
            result = 0
            
            for [x, y] in [(-2, 1),(-1, 2),(1, 2),(2, 1),(2, -1),(1, -2),(-1, -2),(-2, -1)]:
                # r += x
                # col += y
                # result += dfs(nn+1, r, col)
                # r -= x
                # col -= y
                result += dfs(nn+1, r + x, col + y)
            
            return result
        
        result = dfs(0, row, column)

        return result / 8 ** k

Method 2 BFS

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

        dq = deque([[(row, column), 1.0]])

        r0 = 0

        while k != 0:

            lens = len(dq)
            M = defaultdict(float)

            for _ in range(lens):
                (i, j), w = dq.popleft()

                ww = w / 8
                for x, y in [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]:
                    if not (0 <= i + x < n and 0 <= j + y < n):
                        continue

                    M[(i+x, j+y)] += ww

            for key, value in M.items():
                dq.append([key, value])

            k -= 1

        for _, ww in dq:
            r0 += ww

        return r0