Trick 1: How to get rid of TLE for BFS algorithm?

Recently, I participated in a leetcode contest. I got TLE for my BFS solution. After trial and error, I found by changing my BFS code level by level, the TLE can be get rid of.

The problem

1263. Minimum Moves to Move a Box to Their Target Location

Solution 1 (TLE)

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid[0])
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 'S':
                    pi, pj = i, j
                elif grid[i][j] == 'B':
                    bi, bj = i, j
                 
        def dfs_person(i, j, ti, tj, bi, bj):
            seen = set()
            if ti>=R or tj>=C or grid[ti][tj]=='#':return False
            open_list = [(i,j)]
            while open_list:
                i,j = open_list.pop()
                if (i,j)==(ti,tj):return True
                seen.add((i, j))
                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
                        open_list.append((r,c))
            return False                     
                
        def bfs(i, j, pi, pj):
            b_seen = set()
            open_list = [(i,j, pi, pj, 0)]
            for i, j, pi, pj, d in open_list:
                b_seen.add((i,j, pi, pj))
                if grid[i][j] == 'T':return d
                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C and grid[r][c]!='#' and (r,c, i, j) not in b_seen:
                        ti, tj = i-di, j-dj
                        if dfs_person(pi, pj, ti, tj, i, j):
                            open_list.append((r,c,i, j, d+1))    
            return -1
        return bfs(bi, bj, pi, pj)

Solution 2 (Good)

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid[0])
        for i in range(R):
            for j in range(C):
                if grid[i][j] == 'S':
                    pi, pj = i, j
                elif grid[i][j] == 'B':
                    bi, bj = i, j
                 
        def dfs_person(i, j, ti, tj, bi, bj):
            seen = set()
            if ti>=R or tj>=C or grid[ti][tj]=='#':return False
            open_list = [(i,j)]
            while open_list:
                i,j = open_list.pop()
                if (i,j)==(ti,tj):return True
                seen.add((i, j))
                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!='#':
                        open_list.append((r,c))
            return False
                        
                
        def bfs(i, j, pi, pj):
            b_seen = set()
            cur_level = {(i,j, pi, pj, 0)}
            while cur_level:
                nxt_level = set()
                for i, j, pi, pj, d in cur_level:
                    b_seen.add((i,j, pi, pj))
                    if grid[i][j] == 'T':return d
                    for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:
                        r, c = i+di, j+dj
                        if 0<=r<R and 0<=c<C and grid[r][c]!='#' and (r,c, i, j) not in b_seen:
                            ti, tj = i-di, j-dj
                            if dfs_person(pi, pj, ti, tj, i, j):
                                nxt_level.add((r,c,i, j, d+1))
                cur_level = nxt_level      
            return -1
        return bfs(bi, bj, pi, pj)