python – Is this BFS solution ‘slow’ – LeetCode #688

I’m learning competitive programming and came across this question on LeetCode : 688. Knight Probability in Chessboard

On an n x n chessboard, a knight starts at the cell (row, column) and
attempts to make exactly k moves. The rows and columns are 0-indexed,
so the top-left cell is (0, 0), and the bottom-right cell is (n – 1, n-1).

A chess knight has eight possible moves it can make, each move is two cells in a cardinal direction,
then one cell in an orthogonal direction. Each time the knight is to move, it chooses one of eight > possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

I wrote following BFS solution for it

from collections import deque

class Solution:    
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        i = 0
        pos_moves = deque(((r, c, 1)))  # (r, c, prob)
        self.moves_memo = {}
        while i < K and len(pos_moves):
            increase_i_after = len(pos_moves)
            for j in range(increase_i_after):
                move = pos_moves.popleft()
                for next_move in self.get_pos_moves(N, move(0), move(1), move(2)):
                    pos_moves.append((next_move(0), next_move(1), next_move(2)))
            i += 1
        ans = 0
        for m in pos_moves:
            ans += m(2)
        return ans/len(pos_moves) if len(pos_moves) > 0 else 0
    def get_pos_moves(self, n, r, c, prev_p):
        # Returns a list of possible moves
        if (r, c) in self.moves_memo:
            pos_moves = self.moves_memo((r, c))
            pos_moves = deque(())
            if r+2 < n:
                if c+1 < n:
                    pos_moves.append((r+2, c+1, 0))
                if c-1 >= 0:
                    pos_moves.append((r+2, c-1, 0))
            if r+1 < n:
                if c+2 < n:
                    pos_moves.append((r+1, c+2, 0))
                if c-2 >= 0:
                    pos_moves.append((r+2, c-2, 0))
            if r-2 >= 0:
                if c+1 < n:
                    pos_moves.append((r-2, c+1, 0))
                if c-1 >= 0:
                    pos_moves.append((r-2, c-1, 0))
            if r-1 >= 0:
                if c+2 < n:
                    pos_moves.append((r-1, c+2, 0))
                if c-2 >= 0:
                    pos_moves.append((r-1, c-2, 0))
            self.moves_memo((r, c)) = pos_moves
        l = len(pos_moves)
        if l == 0:
            return pos_moves
            for move in pos_moves:
                move(2) = prev_p*l/8       
            return pos_moves

For n = 8, K = 30, r = 6, c = 4, this solution exceeds time limits. I am not able to figure out why is this solution less time efficient than this. I’m looking for reasons why my code is ‘slow’. Thank you!