Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by a grid of size m x n, where each element is a wall, floor, or a box.
Your task is move the box 'B' to the target position 'T' under the following rules:

Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle  (impossible to walk there). 
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.
 
Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:
Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:
Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

 
Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 20
1 <= n <= 20
grid contains only characters '.', '#',  'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.

Difficulty: interview

Starter code:

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        

Solutions:
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n, g = len(grid), len(grid[0]), collections.defaultdict(list)
        for i in range(m):
            for j in range(n):
                g[grid[i][j]] += [complex(i, j)]
        
        def f(b, s):
            nonlocal time
            time += 1
            boxToTarget = b - target
            return (abs((boxToTarget.real))+abs((boxToTarget).imag)+s, abs(boxToTarget), time)
        
        player, box, target, time = *g['S'], *g['B'], *g['T'], 1
        floor = {player, box, target, *g['.']}
        
        alpha = [(f(box, 1), 1, player, box)]
        directions, visited = (1, -1, 1j, -1j), set()   # 下上右左
        
        # 因为都不是数而是复数。因此采用字典映射的方式定义low dfn
        low = dict.fromkeys(floor, 0)  # 标准的dict.fromkeys创建字典。keys来源第一个参数第二个参数默认或赋值
        dfn = low.copy()
        count = 0
        index = {}
        # 标准无向图tarjan深度优先扩展函数，参数currIndex为当前拓展点，记录拓展的父节点防止重复拓展
        def tarjan(currIndex, parentIndex):
            nonlocal count
            count += 1
            dfn[currIndex] = low[currIndex] = count
            index[count] = currIndex
            for direction in directions:
                nextIndex = currIndex + direction
                if nextIndex in floor and nextIndex != parentIndex:
                    if not low[nextIndex]:
                        tarjan(nextIndex, currIndex)
                    low[currIndex] = min(low[currIndex], low[nextIndex])
        
        #运行tarjan函数，初始值为box的坐标，因为坐标都在复平面第一象限，初始父节点取-1不影响计算
        tarjan(box, -1)
        #print(low)
        #print(dfn)
        # 如果箱子在割点上仍可以移动的话，则箱子在移动的过程中，人的坐标也完成了强连通分量的转移，
        # 所以即便是宽度为1的碎片化的强连通分量隧道，也不影响上述结论。
        for currIndex in floor:  # 所有的可达点
            connect = [currIndex]
            while dfn[connect[-1]] != low[connect[-1]]:
                connect.append(index[low[connect[-1]]])
            for w in connect[:-2]:
                low[w] = low[connect[-1]]
        #print(low)
        
        # 计算完强连通分量后可以加一个剪枝，即如果人或目标点没被计算到，则表示三个关键点不在同一个并查集里面，
        # 可以直接返回-1
        if not low[player] * low[target]:
            return -1
        
        while alpha:
            _, steps, currPlayer, currBox = heapq.heappop(alpha)
            for direction in directions:
                nextPlayer, nextBox = currBox - direction, currBox + direction
                if nextBox in floor and nextPlayer in floor and (nextPlayer, currBox) not in visited and low[currPlayer] == low[nextPlayer]:
                    if nextBox == target:
                        return steps
                    heapq.heappush(alpha, (f(nextBox, steps + 1), steps + 1, currBox, nextBox))
                    visited.add((nextPlayer, currBox))
        return -1



class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n, g = len(grid), len(grid[0]), collections.defaultdict(list)
        for i in range(m):
            for j in range(n):
                g[grid[i][j]] += [complex(i, j)]
        
        def f(b, s):
            nonlocal time
            time += 1
            boxToTarget = b - target
            return (abs((boxToTarget.real))+abs((boxToTarget).imag)+s, abs(boxToTarget), time)
        
        player, box, target, time = *g['S'], *g['B'], *g['T'], 1
        floor = {player, box, target, *g['.']}
        
        alpha = [(f(box, 1), 1, player, box)]
        directions, visited = (1, -1, 1j, -1j), set()   # 下上右左
        
        # 因为都不是数而是复数。因此采用字典映射的方式定义low dfn
        low = dict.fromkeys(floor, 0)  # 标准的dict.fromkeys创建字典。keys来源第一个参数第二个参数默认或赋值
        dfn = low.copy()
        count = 0
        index = {}
        # 标准无向图tarjan深度优先扩展函数，参数currIndex为当前拓展点，记录拓展的父节点防止重复拓展
        def tarjan(currIndex, parentIndex):
            nonlocal count
            count += 1
            dfn[currIndex] = low[currIndex] = count
            index[count] = currIndex
            for direction in directions:
                nextIndex = currIndex + direction
                if nextIndex in floor and nextIndex != parentIndex:
                    if not low[nextIndex]:
                        tarjan(nextIndex, currIndex)
                    low[currIndex] = min(low[currIndex], low[nextIndex])
        
        #运行tarjan函数，初始值为box的坐标，因为坐标都在复平面第一象限，初始父节点取-1不影响计算
        tarjan(box, -1)
        #print(low)
        #print(dfn)
        # 如果箱子在割点上仍可以移动的话，则箱子在移动的过程中，人的坐标也完成了强连通分量的转移，
        # 所以即便是宽度为1的碎片化的强连通分量隧道，也不影响上述结论。
        for currIndex in floor:  # 所有的可达点
            connect = [currIndex]
            while dfn[connect[-1]] != low[connect[-1]]:
                connect.append(index[low[connect[-1]]])
            for w in connect[:-2]:
                low[w] = low[connect[-1]]
        #print(low)
        
        # 计算完强连通分量后可以加一个剪枝，即如果人或目标点没被计算到，则表示三个关键点不在同一个并查集里面，
        # 可以直接返回-1
        if not low[player] * low[target]:
            return -1
        
        while alpha:
            _, steps, currPlayer, currBox = heapq.heappop(alpha)
            for direction in directions:
                nextPlayer, nextBox = currBox - direction, currBox + direction
                if nextBox in floor and nextPlayer in floor and (nextPlayer, currBox) not in visited and low[currPlayer] == low[nextPlayer]:
                    if nextBox == target:
                        return steps
                    heapq.heappush(alpha, (f(nextBox, steps + 1), steps + 1, currBox, nextBox))
                    visited.add((nextPlayer, currBox))
        return -1



class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:

        # this loop is to get the coordinates of target, box and person. Nothing else is gained here
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i,j)
                if grid[i][j] == \"B\":
                    box = (i,j)
                if grid[i][j] == \"S\":
                    person = (i,j)

        # this function checks whether the given coordinates/indices are valid to go
        def valid(x,y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'

        # this function checks whether the person can travel from current postition to destination position.
        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.
        def check(curr,dest,box):
            que = deque([curr])
            v = set()
            while que:
                pos = que.popleft()
                if pos == dest: return True
                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]
                for x,y in new_pos:
                    if valid(x,y) and (x,y) not in v and (x,y)!=box:
                        v.add((x,y))
                        que.append((x,y))
            return False

        q = deque([(0,box,person)])
        vis = {box+person}
        # this is the main bfs which gives us the answer
        while q :
            dist, box, person = q.popleft()
            if box == target: # return the distance if box is at the target
                return dist

            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]

            for new_box,new_person in zip(b_coord,p_coord): 
                # we check if the new box coordinates are valid and our current state is not in vis
                if valid(*new_box) and new_box+box not in vis:
                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates
                    if valid(*new_person) and check(person,new_person,box):
                        vis.add(new_box+box)
                        q.append((dist+1,new_box,box))

        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        num_rows = len(grid)
        num_cols = len(grid[0])
        for r in range(num_rows):
            for c in range(num_cols):
                if grid[r][c] == 'T':
                    target_row, target_col = r, c
                    grid[r][c] = '.'
                elif grid[r][c] in 'B':
                    box_row, box_col = r, c
                    grid[r][c] = '.'
                elif grid[r][c] in 'S':
                    src_row, src_col = r, c
                    grid[r][c] = '.'
        def traversal(player_row, player_col, box_row, box_col, visited):
            if not (0 <= player_row < num_rows and 0 <= player_col < num_cols):
                return visited
            if grid[player_row][player_col] != '.' or (player_row, player_col) in visited:
                return visited
            visited.add((player_row, player_col))
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_player_row = player_row + i
                new_player_col = player_col + j
                if new_player_row != box_row or new_player_col != box_col:
                    traversal(new_player_row, new_player_col, box_row, box_col, visited)
            return visited
        queue = deque([(src_row, src_col, box_row, box_col, 0)])
        visited = {(src_row, src_col, box_row, box_col)}
        while queue:
            curr_row, curr_col, box_row, box_col, num_pushs = queue.popleft()
            reachable = traversal(curr_row, curr_col, box_row, box_col, set())
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_box_row = box_row+i
                new_box_col = box_col+j
                if not (0 <= new_box_row < num_rows and 0 <= new_box_col < num_cols):
                    continue
                if grid[new_box_row][new_box_col] != '.':
                    continue
                if (box_row - i, box_col - j) in reachable and (box_row, box_col, new_box_row, new_box_col) not in visited:
                    visited.add((box_row, box_col, new_box_row, new_box_col))
                    if new_box_row == target_row and new_box_col == target_col:
                        return num_pushs + 1
                    queue.append((box_row, box_col, new_box_row, new_box_col, num_pushs + 1))
        return -1


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def move(node, dx, dy):
            px, py, bx, by, dist = node
            px += dx
            py += dy
            illegal = (-1, -1, -1, -1, -1)
            if px < 0 or px >= m or py < 0 or py >= n or grid[px][py] == \"#\":
                return illegal
            if px == bx and py == by:
                bx += dx
                by += dy
                if bx < 0 or bx >= m or by < 0 or by >= n or grid[bx][by] == \"#\":
                    return illegal
                return (px, py, bx, by, dist+1)
            if grid[px][py] == \".\":
                return (px, py, bx, by, dist)
        
        player, target, box = [], [], []
        for r in range(m):
            for c in range(n):
                if grid[r][c] == \"S\":
                    player = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"T\":
                    target = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"B\":
                    box = (r, c)
                    grid[r][c] = \".\"
        
        queue = collections.deque()
        queue.append((player[0], player[1], box[0], box[1], 0))
        visited = collections.defaultdict(lambda: float(\"inf\"))
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        res = float(\"inf\")
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                px, py, bx, by, dist = node
                if (bx, by) == target:
                    res = min(res, dist)
                if dist < visited[(px, py, bx, by)]:
                    visited[(px, py, bx, by,)] = dist
                else:
                    continue
                for dx, dy in directions:
                    newNode = move(node, dx, dy)
                    px2, py2, bx2, by2, dist2 = newNode
                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:
                        queue.append(newNode)
                    
        
        return res if res < float(\"inf\") else -1
    
    
    
    
    
    
        
        
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        
        def move(tup, d):
            roffset, coffset = d
            pr,pc,br,bc,dist = tup
            pr += roffset
            pc += coffset
            illegal = (-1,-1,-1,-1,-1)
            if pr<0 or pr>=nrow or pc<0 or pc>= ncol or grid[pr][pc]==\"#\":
                return illegal
            if pr==br and pc==bc:
                br += roffset
                bc += coffset
                if br<0 or br>=nrow or bc<0 or bc>=ncol or grid[br][bc]==\"#\":
                    return illegal
                return (pr,pc,br,bc,dist+1)
            if grid[pr][pc] == \".\":
                return (pr,pc,br,bc,dist)
        
        p,t,b = [],[],[]
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == \"S\":
                    p = (r,c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"T\":
                    t = (r,c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"B\":
                    b = (r,c)
                    grid[r][c] = \".\"
                    
        q = collections.deque()
        q.append((p[0],p[1],b[0],b[1],0))
        visited = collections.defaultdict(lambda: float(\"inf\"))
        ret = float(\"inf\")
        while q:
            for _ in range(len(q)):
                tup = q.popleft()
                pr,pc,br,bc,dist = tup
                if (br,bc) == t:
                    ret = min(ret, dist)
                if dist < visited[(pr,pc,br,bc)]:
                    visited[(pr,pc,br,bc)] = dist
                else:
                    continue
                for d in [(-1,0),(1,0),(0,1),(0,-1)]:
                    tup2 = move(tup, d)
                    pr2,pc2,br2,bc2,dist2 = tup2
                    if pr2 != -1 and dist2 < visited[(pr2,pc2,br2,bc2)]:
                        q.append(tup2)
        return ret if ret < float(\"inf\") else -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        queue = deque()
        m = len(grid)
        n = len(grid[0])
        visited = {}
        
        rq = deque()
        reach = {}
        startx, starty  = -1,-1
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    rq.append([i,j])
                    startx, starty = i,j   
        
                    
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    queue.append([i,j, 0, startx, starty])
                    visited[(i,j, startx, starty)] = 1       
                    
        
        while(len(queue) > 0):
            x, y,  step, startx, starty = queue.popleft()
            
            #print(x, y, step, grid[x][y])
            if grid[x][y] == 'T':
                return step

            rq = deque()
            reach = {}
            rq.append([startx, starty])
            while(len(rq) > 0):
                rx, ry = rq.popleft()
                reach[(rx, ry)] = 1
                for deltax, deltay in [[-1,0],[1,0],[0,-1],[0,1]]:
                    nx, ny = rx+deltax, ry+deltay
                    if nx >= 0 and nx<m and ny >=0 and ny < n:
                        if grid[nx][ny] != '#' and (nx,ny) != (x,y)  and (nx,ny) not in reach:
                            rq.append([nx,ny])
                            reach[(nx,ny)] = 1
            
            
            
            for deltax, deltay in [[-1,0],[1,0],[0,-1],[0,1]]:
                nx, ny = x + deltax, y + deltay
                otherx, othery = x-deltax, y-deltay
                
                if nx >= 0 and nx<m and ny >=0 and ny < n and otherx >=0 and otherx <m and othery >=0 and othery < n:
                    if grid[nx][ny] != '#' and grid[otherx][othery] != '#':
                        if (nx, ny,otherx, othery) not in visited and (otherx,othery) in reach:
                            queue.append([nx, ny, step+1, otherx, othery])
                            visited[(nx,ny,otherx, othery)] = 1
            
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 'T':
                    target = (r,c)
                if grid[r][c] == 'S':
                    start_person = (r,c)
                if grid[r][c] == 'B':
                    start_box = (r,c)
            
        def heuristic(box):
            return abs(target[0]-box[0]) + abs(target[1]-box[1])

        def out_bounds(location):
            r,c=location
            return r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == '#'

        heap = [[heuristic(start_box), 0, start_person, start_box]]
        vis = set()
        while heap:
            _, moves, person, box = heapq.heappop(heap)
            if box == target:
                return moves
            if (person, box) in vis:
                continue
            vis.add((person, box))

            for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_person = (person[0]+dr,person[1]+dc)
                if out_bounds(new_person):
                    continue

                if new_person == box:
                    new_box = (box[0]+dr, box[1]+dc)
                    if out_bounds(new_box):
                        continue
                    heapq.heappush(heap, [heuristic(new_box)+moves+1, moves+1, new_person, new_box])
                else:
                    heapq.heappush(heap, [heuristic(box)+moves, moves, new_person, box])

        return -1
                        
                    
                    
                    
                    


import heapq

def valid(grid, r, c):
    max_r, max_c = len(grid)-1, len(grid[0])-1
    
    if 0 <= r <= max_r and 0 <= c <= max_c and grid[r][c] != \"#\":
        return True
    
    return False

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == \"S\":
                    s_r, s_c = r, c
                if grid[r][c] == \"B\":
                    b_r, b_c = r,c
                if grid[r][c] == \"T\":
                    target = (r,c)
        
        min_queue = [(0, s_r, s_c, b_r, b_c)]
        visited = set()
        directions = ((1,0), (-1, 0), (0,1), (0,-1))
        
        while len(min_queue) > 0:
            cost, s_r, s_c, b_r, b_c = heapq.heappop(min_queue)
            
            if (b_r, b_c) == target:
                return cost
            
            if (s_r, s_c, b_r, b_c) in visited:
                continue
                
            visited.add((s_r, s_c, b_r, b_c))
            
            for dr, dc in directions:
                new_cost = cost
                ns_r, ns_c = s_r + dr, s_c + dc
                nb_r, nb_c = b_r, b_c
                
                if (ns_r, ns_c) == (nb_r, nb_c):
                    new_cost +=1
                    nb_r, nb_c = nb_r + dr, nb_c + dc
                    
                new_state = (ns_r, ns_c, nb_r, nb_c)
                
                if valid(grid, ns_r, ns_c) and valid(grid, nb_r, nb_c) and new_state not in visited:
                    heapq.heappush(min_queue, (new_cost, *new_state))
                
        return -1
                

from queue import deque


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        def isValid(pos):
            i, j = pos[0], pos[1]
            return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] != '#'
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'T':
                    target = (i, j)
                elif grid[i][j] == 'B':
                    box = (i, j)
                elif grid[i][j] == 'S':
                    player = (i, j)

        def personCanMove(pos, dest, box):
            que = deque([pos])
            seen = {pos}
            while que:
                p = que.popleft()
                if p == dest:
                    return True
                i, j = p[0], p[1]
                nextPos = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
                for nextI, nextJ in nextPos:
                    if isValid((nextI, nextJ)) and (nextI, nextJ) not in seen and (nextI, nextJ) != box:
                        seen.add((nextI, nextJ))
                        que.append((nextI, nextJ))
            return False
        q = deque([(box, player, 0)])
        seen = {box + player}
        while q:
            b, p, pushes = q.popleft()
            if b == target:
                return pushes
            nextBArr = [(b[0]-1, b[1]), (b[0]+1, b[1]),
                        (b[0], b[1]+1), (b[0], b[1]-1)]
            pushPosArr = [(b[0]+1, b[1]), (b[0]-1, b[1]),
                          (b[0], b[1]-1), (b[0], b[1]+1)]
            for nextB, pushPos in zip(nextBArr, pushPosArr):
                if isValid(nextB) and nextB+b not in seen:
                    if isValid(pushPos) and personCanMove(p, pushPos, b):
                        q.append((nextB, b, pushes + 1))
                        seen.add(nextB + b)
        return -1


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return -1
        
        # Main idea: run Dijkstra's except only expand on nodes
        # that do not have a wall on the oposite side of the
        # box location.
        self.grid = grid
        dst = None
        start = None
        box_start = None
        from queue import PriorityQueue
        pq = PriorityQueue()
        for row in range(len(grid)):
            for col in range(len(grid[row])):
                elem = grid[row][col]
                if elem == \"B\":
                    box_start = (row, col)
                elif elem == \"T\":
                    dst = (row, col)
                elif elem == \"S\":
                    start = (row, col)
        
        assert dst is not None
        assert start is not None
        assert box_start is not None
        pq.put((0, box_start[0], box_start[1], start))
        
        best = {}
        while not pq.empty():
            pushes, row, col, start = pq.get()
            if (row, col, start) not in best or best.get((row, col, start), float(\"inf\")) > pushes:
                best[(row, col, start)] = pushes
                if (row, col) == dst:
                    return pushes
                if row + 1 < len(grid) and row - 1 >= 0:
                    if grid[row + 1][col] != \"#\" and grid[row - 1][col] != \"#\" and self.dfs(start[0], start[1], (row +1, col), set(), (row, col)):
                        pq.put((pushes + 1, row - 1, col, (row, col)))
                    if grid[row - 1][col] != \"#\" and grid[row + 1][col] != \"#\" and self.dfs(start[0], start[1], (row - 1, col), set(), (row, col)):
                        pq.put((pushes + 1, row + 1, col, (row, col)))
                if col + 1 < len(grid[0]) and col - 1 >= 0:
                    if grid[row][col + 1] != \"#\" and grid[row][col - 1] != \"#\" and self.dfs(start[0], start[1], (row , col + 1), set(), (row, col)):
                        pq.put((pushes + 1, row, col - 1, (row, col)))
                    if grid[row][col - 1] != \"#\" and grid[row][col + 1] != \"#\" and self.dfs(start[0], start[1], (row , col - 1), set(), (row, col)):
                        pq.put((pushes + 1, row, col + 1, (row, col)))
        return -1
    
    def dfs(self, r, c, goal, seen, box_location):
        if (r, c) == goal:
            return True
        if not (0 <= r < len(self.grid)):
            return False
        if not (0 <= c < len(self.grid[0])):
            return False
        if self.grid[r][c] == \"#\":
            return False
        if (r, c) == box_location:
            return False
        if (r, c) not in seen:
            seen.add((r, c))
            if self.dfs(r + 1, c, goal, seen, box_location):
                return True
            if self.dfs(r - 1, c, goal, seen, box_location):
                return True
            if self.dfs(r, c + 1, goal, seen, box_location):
                return True
            if self.dfs(r, c - 1, goal, seen, box_location):
                return True
        return False

from collections import deque
directions = [[0,-1], [0,1], [-1, 0], [1,0]]
def can_move(source,dest, a, walls, box):
    q = deque()
    q.append(source)
    visited = set()
    while q:
        item = q.popleft()
        if item == dest:
            return True
        if item in visited:
            continue
        visited.add(item)
        for direction in directions:
            new_item = (item[0]+direction[0], item[1]+direction[1])
            if is_valid(a, new_item, walls, box):
                q.append(new_item)
                
def is_valid(a, pos,walls,box=''):
    x, y = pos
    if 0<=x<len(a) and  0<=y<len(a[0]) and  (x,y) not in walls and (x,y) != box:
        return True
    return False
    
    
        
def get_info(a):
    walls=set()
    for i in range(len(a)):
        for j in range(len(a[0])):
            if a[i][j] == '#':
                walls.add((i,j))
            if a[i][j] == 'S':
                person = (i,j)
            if a[i][j] == 'T':
                target = (i,j)
            if a[i][j] == 'B':
                box = (i,j)
    return person, target, box, walls

def get_min_moves(a):
    person, target, box, walls = get_info(a)
    q = deque()
    q.append((0, box, person))
    result = float('inf')
    visited = set()
    while q:
        dist, box, person = q.popleft()
        if (box,person) in visited:
            continue
        visited.add((box,person))
        if box == target:
            result =min(result, dist)
            continue
        for direction in directions:
            new_player_position  = (box[0] +direction[0], box[1] +direction[1])
            new_box = (box[0] +direction[0]*-1, box[1] +direction[1]*-1) 
            if is_valid(a, new_box, walls) and can_move(person, new_player_position, a, walls, box):
                if is_valid(a,new_player_position, walls):
                    q.append((dist + 1, new_box, box))
    return result if result != float('inf') else -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        return get_min_moves(grid)

import heapq

class Solution:
  def minPushBox(self, grid: List[List[str]]) -> int:
    # bfs, dfs, a-star search
    # key:
    # represent the state using (xb, yb, xp, yp), box and storekeeper coordinates, where storekeeper can move around,
    # up down left and right, and push the box when storekeeper move to box position and the cell next to it is empty.
    m, n = len(grid), len(grid[0])
    xb, yb, xs, ys, xt, yt = -1, -1, -1, -1, -1, -1
    for x in range(m):
      for y in range(n):
        if grid[x][y] == 'B':
          xb, yb = x, y
          grid[x][y] = '.'
        if grid[x][y] == 'S':
          xs, ys = x, y
          grid[x][y] = '.'
        if grid[x][y] == 'T':
          xt, yt = x, y
          grid[x][y] = '.'
    # a-star search
    # heuristic: h(box, target) = abs(xb - xt) + abs(yb - yt), as the lower bound of moves to push box to target.
    # init
    q, seen = [(abs(xb - xt) + abs(yb - yt) + 0, 0, xb, yb, xs, ys)], set()
    while q:
      h, d, xb, yb, xs, ys = heapq.heappop(q)
      if (xb, yb) == (xt, yt):
        return d
      if (xb, yb, xs, ys) not in seen:
        seen.add((xb, yb, xs, ys))
        # storekeeper moves around and pushes the box when step into box coordinates
        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
          xr, yr = xs + dx, ys + dy
          if 0 <= xr < m and 0 <= yr < n and grid[xr][yr] == '.':
            if (xr, yr) == (xb, yb):
              xc, yc = xb + dx, yb + dy
              if 0 <= xc < m and 0 <= yc < n and grid[xc][yc] == '.':
                heapq.heappush(q, (abs(xc - xt) + abs(yc - yt) + d + 1, d + 1, xc, yc, xr, yr))
            else:
              heapq.heappush(q, (h, d, xb, yb, xr, yr))
    return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == \"T\":
                    target = (r, c)
                if grid[r][c] == \"B\":
                    start_box = (r, c)
                if grid[r][c] == \"S\":
                    start_person = (r, c)
                    
        def heuristic(box):
            return abs(target[0] - box[0]) + abs(target[1] - box[1])
        
        def out_bounds(location):  # return whether the location is in the grid and not a wall
            r, c = location
            if r < 0 or r >= rows:
                return True
            if c < 0 or c >= cols:
                return True
            return grid[r][c] == \"#\"
                        
        heap = [[heuristic(start_box), 0, start_person, start_box]]
        visited = set()
        
        while heap:
            _, moves, person, box = heapq.heappop(heap)
            if box == target:
                return moves
            if (person, box) in visited: # do not visit same state again
                continue
            visited.add((person, box))
            
            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                new_person = (person[0] + dr, person[1] + dc)
                if out_bounds(new_person):
                    continue
                    
                if new_person == box:
                    new_box = (box[0] + dr, box[1] + dc)
                    if out_bounds(new_box):
                        continue
                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
                else:
                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same
        
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        
        def move(tup, d):
            roffset, coffset = d
            pr, pc, br, bc, dist = tup
            pr += roffset
            pc += coffset
            illegal = (-1, -1, -1, -1, -1)
            if pr < 0 or pr >= nrow or pc < 0 or pc >= ncol or grid[pr][pc] == \"#\":
                return illegal
            if pr == br and pc == bc:
                br += roffset
                bc += coffset
                if br < 0 or br >= nrow or bc < 0 or bc >= ncol or grid[br][bc] == \"#\":
                    return illegal
                return (pr, pc, br, bc, dist+1)
            if grid[pr][pc] == \".\":
                return (pr, pc, br, bc, dist)
        
        p, t, b = [], [], []
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == \"S\":
                    p = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"T\":
                    t = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"B\":
                    b = (r, c)
                    grid[r][c] = \".\"
        
        q = collections.deque()
        q.append((p[0], p[1], b[0], b[1], 0))
        visited = collections.defaultdict(lambda: float(\"inf\"))
        ret = float(\"inf\")
        while q:
            for _ in range(len(q)):
                tup = q.popleft()
                pr, pc, br, bc, dist = tup
                if (br, bc) == t:
                    ret = min(ret, dist)
                if dist < visited[(pr, pc, br, bc)]:
                    visited[(pr, pc, br, bc)] = dist
                else:
                    continue
                for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    tup2 = move(tup, d)
                    pr2, pc2, br2, bc2, dist2 = tup2
                    if tup2[0] != -1 and dist2 < visited[(pr2, pc2, br2, bc2)]:
                        q.append(tup2)
                    
        
        return ret if ret < float(\"inf\") else -1

class Solution:

    def packString(self, box_row, box_col, player_row, player_col):
        return str(box_row) + \",\" + str(box_col) + \",\" + str(player_row) + \",\" + str(player_col)

    def unpackString(self, state):
        return list(map(int, state.split(\",\")))

    def posAvailable(self, grid, row, col):
        if(row < 0 or row >= len(grid)):
            return False
        
        if(col < 0 or col >= len(grid[0])):
            return False
        
        if(grid[row][col] == \"#\"):
            return False
        
        return True

    def minPushBox(self, grid):
        #Setup
        box_row = -1
        box_col = -1
        player_row = -1
        player_col = -1
        target_row = -1
        target_col = -1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if(grid[i][j] == \"B\"):
                    box_row = i
                    box_col = j
                elif(grid[i][j] == \"S\"):
                    player_row = i
                    player_col = j
                elif(grid[i][j] == \"T\"):
                    target_row = i
                    target_col = j
        memory = {}
        distances = {}

        moves = [ (0,1), (0, -1), (1, 0), (-1,0) ]
        state = self.packString(box_row, box_col, player_row, player_col)
        queue = [ [state] ]

        distances[state] = 0
        
        dist = 0
        while(dist < len(queue)):
            while(queue[dist]):
                state = queue[dist].pop(0)

                if(state in memory):
                    continue
                memory[state] = 1

                [box_row, box_col, player_row, player_col] = self.unpackString(state)

                if(box_row == target_row and box_col == target_col):
                    return dist

                for move in moves :
                    new_player_row = player_row + move[0]
                    new_player_col = player_col + move[1]

                    if not self.posAvailable(grid, new_player_row, new_player_col):
                        continue

                    if(new_player_row == box_row and new_player_col == box_col):
                        L = 1
                        new_box_row = box_row + move[0]
                        new_box_col = box_col + move[1]
                    else:
                        L = 0
                        new_box_row = box_row
                        new_box_col = box_col
                    
                    if(not self.posAvailable(grid, new_box_row, new_box_col)):
                        continue

                    new_state = self.packString(new_box_row, new_box_col, new_player_row, new_player_col)

                    curr_distance = distances[state] + L
                    if(new_state not in distances or curr_distance < distances[new_state]):
                        distances[new_state] = curr_distance
                        while(len(queue) <= curr_distance):
                            queue.append([])
                        queue[curr_distance].append(new_state)
            dist += 1
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == \"T\":
                    target = (r, c)
                if grid[r][c] == \"B\":
                    start_box = (r, c)
                if grid[r][c] == \"S\":
                    start_person = (r, c)
                    
        def heuristic(box):
            # return abs(target[0] - box[0]) + abs(target[1] - box[1])
            return 0;
        
        def out_bounds(location):  # return whether the location is in the grid and not a wall
            r, c = location
            if r < 0 or r >= rows:
                return True
            if c < 0 or c >= cols:
                return True
            return grid[r][c] == \"#\"
                        
        heap = [[heuristic(start_box), 0, start_person, start_box]]
        visited = set()
        
        while heap:
            _, moves, person, box = heapq.heappop(heap)
            if box == target:
                return moves
            if (person, box) in visited: # do not visit same state again
                continue
            visited.add((person, box))
            
            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                new_person = (person[0] + dr, person[1] + dc)
                if out_bounds(new_person):
                    continue
                    
                if new_person == box:
                    new_box = (box[0] + dr, box[1] + dc)
                    if out_bounds(new_box):
                        continue
                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
                else:
                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same
        
        return -1

from collections import deque 
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        def can_reach(x, y):
            q = deque([x])
            seen = set([x])
            while q:
                i, j = q.popleft()
                if (i, j) == y:
                    return True
                for di, dj in (-1, 0), (1, 0), (0, 1), (0, -1):
                    i_ = i + di
                    j_ = j + dj
                    if 0 <= i_ < m and 0 <= j_ < n and (i_, j_) not in seen and grid[i_][j_] == '.':
                        seen.add((i_, j_))
                        q.append((i_, j_))
            return False
            
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'T':
                    t = (i, j)
                    grid[i][j] = '.'
                if grid[i][j] == 'B':
                    b = (i, j)
                    grid[i][j] = '.'
                if grid[i][j] == 'S':
                    s = (i, j)
                    grid[i][j] = '.'
        depth = 0
        q = deque([(b, s)])
        seen = set([(b, s)])
        
        while q:
            depth += 1
            for _ in range(len(q)):
                b, s = q.popleft()
                grid[b[0]][b[1]] = 'B'
                for dx, dy in (-1, 0), (1, 0), (0, 1), (0, -1):
                    x, y = b[0]+dx, b[1]+dy
                    bx, by = b[0]-dx, b[1]-dy
                    
                    if 0 <= x <m and 0 <= y < n and 0 <= bx <m and 0 <= by < n and grid[x][y] != '#' and grid[bx][by] != '#' and can_reach(s, (x, y)) and ((bx, by), b) not in seen:
                        seen.add(((bx,by), b))
                        q.append(((bx, by), b))
                        if (bx, by) == t:
                            return depth
                grid[b[0]][b[1]] = '.'
        return -1


from time import time
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        d = dict()
        
        lim1 = len(grid)
        lim2 = len(grid[0])
        
        for i in range(0,lim1):
            for j in range(0,lim2):
                if grid[i][j]!=\"#\":
                    val = (i,j)
                    d[val]=[]
                    if i>0 and grid[i-1][j]!=\"#\":
                        d[val].append((i-1,j))
                    if j>0 and grid[i][j-1]!=\"#\":
                        d[val].append((i,j-1))
                    if i<lim1-1 and grid[i+1][j]!=\"#\":
                        d[val].append((i+1,j))
                    if j<lim2-1 and grid[i][j+1]!=\"#\":
                        d[val].append((i,j+1))
                        
                    if grid[i][j]=='S':
                        start = (i,j)
                    elif grid[i][j]=='T':
                        target = (i,j)
                    elif grid[i][j]=='B':
                        box = (i,j)
        mx = max(lim1,lim2)
        def gotobox(c1,c2,b):
            arr = [[-1 for i in range(0,mx)] for j in range(0,mx)]
            arr[c1[0]][c1[1]]=1
            f = []
            begin = [c1]
            while 1!=-1:
                cache = []
                ###print(f)
                for x in begin:
                    if x in c2 and x not in f:
                        
                        f.append(x)
                        
                        
                    for y in d[x]:
                        
                        ###if y==(2,2):print(1)
                        if y!=b and arr[y[0]][y[1]]==-1:
                            arr[y[0]][y[1]]=1
                            cache.append(y)
                ###print(cache,c2)
                if cache==[]:
                    
                    return f
                
                begin = cache
        arr2 = [[[[-1 for i in range(0,mx)] for j in range(0,mx)] for a in range(0,mx)] for b in range(0,mx)]    
        
        tmp1 = [[start,box,0]]
        while 1!=-1:
            
            tmp2 = []
            
            for x in tmp1:
                
                if arr2[x[0][0]][x[0][1]][x[1][0]][x[1][1]]==-1:
                    arr2[x[0][0]][x[0][1]][x[1][0]][x[1][1]]=1
                    for y in d[x[0]]:

                        if x[1]==target:

                            return x[-1]
                        else:
                            vals = gotobox(x[0],d[x[1]],x[1])

                            if vals ==-1:return -1

                            for z in vals:
                                for a in d[x[1]]:

                                    if (z[0]==a[0] and z[1]==a[1]+2) or (z[0]==a[0] and z[1]==a[1]-2) or (z[1]==a[1] and z[0]==a[0]+2) or (z[1]==a[1] and z[0]==a[0]-2): tmp2.append([z,a,x[2]+1])
                    
                        
            if tmp2==[]:return -1
            tmp1 = tmp2
     
                                
                        
                        
            

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def move(node, dx, dy):
            px, py, bx, by, dist = node
            px += dx
            py += dy

            if px < 0 or px >= m or py < 0 or py >= n or grid[px][py] == \"#\":
                return (-1, -1, -1, -1, -1)
            if px == bx and py == by:
                bx += dx
                by += dy
                if bx < 0 or bx >= m or by < 0 or by >= n or grid[bx][by] == \"#\":
                    return (-1, -1, -1, -1, -1)                
                return (px, py, bx, by, dist+1)
            if grid[px][py] == \".\":
                return (px, py, bx, by, dist)
        
        player, target, box = [], [], []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"S\":
                    player = (i, j)
                    grid[i][j] = \".\"
                if grid[i][j] == \"T\":
                    target = (i, j)
                    grid[i][j] = \".\"
                if grid[i][j] == \"B\":
                    box = (i, j)
                    grid[i][j] = \".\"
        
        queue = collections.deque()
        queue.append((player[0], player[1], box[0], box[1], 0))
        visited = collections.defaultdict(lambda: float(\"inf\"))
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        res = float(\"inf\")
        
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                px, py, bx, by, dist = node
                if (bx, by) == target:
                    res = min(res, dist)
                if dist < visited[(px, py, bx, by)]:
                    visited[(px, py, bx, by)] = dist
                else:
                    continue
                for dx, dy in directions:
                    newNode = move(node, dx, dy)
                    px2, py2, bx2, by2, dist2 = newNode
                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:
                        queue.append(newNode)
                    
        
        return res if res < float(\"inf\") else -1
    
    
    
    
    
    
        
        
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def move(tup, d):
            roffset, coffset = d
            pr, pc, br, bc, dist = tup
            pr += roffset
            pc += coffset
            illegal = (-1, -1, -1, -1, -1)
            if pr < 0 or pr >= m or pc < 0 or pc >= n or grid[pr][pc] == \"#\":
                return illegal
            if pr == br and pc == bc:
                br += roffset
                bc += coffset
                if br < 0 or br >= m or bc < 0 or bc >= n or grid[br][bc] == \"#\":
                    return illegal
                return (pr, pc, br, bc, dist+1)
            if grid[pr][pc] == \".\":
                return (pr, pc, br, bc, dist)
        
        player, t, b = [], [], []
        for r in range(m):
            for c in range(n):
                if grid[r][c] == \"S\":
                    player = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"T\":
                    target = (r, c)
                    grid[r][c] = \".\"
                if grid[r][c] == \"B\":
                    box = (r, c)
                    grid[r][c] = \".\"
        
        queue = collections.deque()
        queue.append((player[0], player[1], box[0], box[1], 0))
        visited = collections.defaultdict(lambda: float(\"inf\"))
        res = float(\"inf\")
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                px, py, bx, by, dist = node
                if (bx, by) == target:
                    res = min(res, dist)
                if dist < visited[(px, py, bx, by)]:
                    visited[(px, py, bx, by,)] = dist
                else:
                    continue
                for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    newNode = move(node, d)
                    px2, py2, bx2, by2, dist2 = newNode
                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:
                        queue.append(newNode)
                    
        
        return res if res < float(\"inf\") else -1
    
    
    
    
    
    
        
        
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m,n=len(grid),len(grid[0])
        dirs=[(0,1),(0,-1),(1,0),(-1,0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='S':
                    S=(i,j)
                if grid[i][j]=='B':
                    B=(i,j)
                if grid[i][j]=='T':
                    T=(i,j)
                    
                    
        def check(x,y):    #判断这个位置是否有效
            return 0<=x<m and 0<=y<n and grid[x][y]!='#'
                    
            
        def canmoveto(e,b,q,visit):          #判断人能否到达目标位置
            while q:
                p=q.pop(0)
                if p==e:
                    return True
                for dx,dy in dirs:
                    nx,ny=p[0]+dx,p[1]+dy
                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:
                        q.append((nx,ny))
                        visit.add((nx,ny))
            return False
        
        def move(e,q,visit):   #判断人能否把箱子推到目标位置
            res = 0
            while q:
                for _ in range(len(q)):
                    b, p = q.pop(0)
                    if b == e:
                        return res
                    
                    for i, j in dirs:
                        nx, ny = b[0] + i, b[1] + j #
                        if check(nx, ny) and \\
                            check(b[0] - i, b[1] - j) and\\
                            ((nx, ny), b) not in visit and \\
                            canmoveto((b[0] - i, b[1] - j), b, [p], set([p])):
                            q.append(((nx, ny), b))
                            visit.add(((nx, ny), b))
                res += 1
            return -1
        return move(T,[(B,S)],set([(B,S)]))
                        
                
                
        
        

class Solution:
    def minPushBox(self, grid) -> int:
        from collections import deque
        r, c = len(grid), len(grid[0])
        di = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def bfs(sx, sy, ex, ey, path):
            t = deque()
            s = set()
            s.add(str((sx, sy)))
            t.append([sx, sy])
            while t:
                x, y = t.popleft()
                if x == ex and y == ey:
                    return True
                for i, j in di:
                    ti = x + i
                    tj = y + j
                    if (0 <= ti < r and 0 <= tj < c 
                        and path[ti][tj] == '.'
                        and str((ti, tj)) not in s):
                        s.add(str((ti, tj)))
                        t.append([ti, tj])
            return False

        bx = by = sx = sy = tx = ty = -1
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 'B':
                    bx, by = i, j
                    grid[i][j] = '.'
                if grid[i][j] == 'S':
                    sx, sy = i, j
                    grid[i][j] = '.'
                if grid[i][j] == 'T':
                    tx, ty = i, j
                    grid[i][j] = '.'

        if -1 in [bx, by, sx, sy, tx, ty]:
            return -1

        t = deque()
        s = set()
        t.append([bx, by, sx, sy, 0])
        s.add(str((bx, by, sx, sy)))

        while t:
            bx, by, sx, sy, step = t.popleft()
            if bx == tx and by == ty:
                return step
            grid[bx][by] = 'B'
            for i, j in di:
                ti = bx + i
                tj = by + j
                tii = bx - i
                tjj = by - j
                if (0 <= ti < r and 0 <= tj < c and grid[ti][tj] == '.'
                    and str((ti, tj, bx, by)) not in s and 0 <= tii < r
                    and 0 <= tjj < c and grid[tii][tjj] == '.' 
                    and bfs(sx, sy, tii, tjj, grid)):
                    t.append([ti, tj, bx, by, step + 1])
                    s.add(str((ti, tj, bx, by)))

            grid[bx][by] = '.'

        return -1


from heapq import *
class Solution:
    MOVES = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"S\": playerPos = (i, j)
                if grid[i][j] == \"B\": boxPos = (i, j)
                if grid[i][j] == \"T\": targetPos = (i, j)
        
        steps = [[999999] * n for _ in range(m)]     # 记录从source/boxPos到(i, j)的步数，这个extra space在A*是必须的，用空间换时间
        steps[boxPos[0]][boxPos[1]] = 0
        
        hq = []
        visited = set()     # 其实A*算法里面也可以不用加visited, 因为每次都是朝曼哈顿最小的方向走的，很少会重复访问同一个节点，不像bfs会经常访问到同一个节点
        heappush(hq, (abs(boxPos[0]-targetPos[0]) + abs(boxPos[1]-targetPos[1]), 0, boxPos, playerPos)) 
        while hq:
            hueristicEstimation, step, currBoxPos, currPlayerPos = heappop(hq)
            if currBoxPos == targetPos:
                return steps[currBoxPos[0]][currBoxPos[1]]

            for move in self.MOVES:
                nextBoxPos_x, nextBoxPos_y = currBoxPos[0] + move[0], currBoxPos[1] + move[1]
                oppositeNextBoxPos_x, oppositeNextBoxPos_y = currBoxPos[0] - move[0], currBoxPos[1] - move[1]
                nextBoxPos = (nextBoxPos_x, nextBoxPos_y)
                oppositeNextBoxPos = (oppositeNextBoxPos_x, oppositeNextBoxPos_y)
                if nextBoxPos_x < 0 or nextBoxPos_x >= m or nextBoxPos_y < 0 or nextBoxPos_y >= n:
                    continue
                if grid[nextBoxPos_x][nextBoxPos_y] == \"#\":
                    continue
                if (nextBoxPos, currBoxPos) in visited:
                    continue
                if not self.playerCanReach(grid, currPlayerPos, oppositeNextBoxPos, currBoxPos):
                    continue
                heappush(hq, (step + abs(nextBoxPos[0]-targetPos[0]) + abs(nextBoxPos[1]-targetPos[1]), step + 1, nextBoxPos, currBoxPos)) 
                visited.add((nextBoxPos, currBoxPos))    # visited里面应该装入(boxPos, the pos where the boxPos comes from)
                steps[nextBoxPos[0]][nextBoxPos[1]] = step + 1
                    
        return -1
                    
    def playerCanReach(self, grid, startPos, endPos, boxPos):
        \"\"\"
        use manhatan distance as Heuristic esitimation for A-star algorithm: steps + (abs(nextPos[0]-endPos[0]) + abs(nextPos[1]-endPos[1])).  
        put the heuristic estimation in the hq, together with steps, so the hq stores 
        (heristic estimation of the minimum steps needed from source to target, steps, nextPos). 
        \"\"\"
        m, n = len(grid), len(grid[0])
        steps = [[999999] * n for _ in range(m)]     # 记录从source/boxPos到(i, j)的步数，这个extra space在A*是必须的，用空间换时间
        steps[startPos[0]][startPos[1]] = 0
        hq = []
        visited = set()
        heappush(hq, (abs(startPos[0] - endPos[0]) + abs(startPos[1] - endPos[1]), 0, startPos))
        visited.add(startPos)
        while hq:
            hueristicEstimation, step, currPos = heappop(hq)
            if currPos == endPos:
                return True
            for move in self.MOVES:
                nextPos_x, nextPos_y = currPos[0] + move[0], currPos[1] + move[1]
                nextPos = (nextPos_x, nextPos_y)
                if nextPos_x < 0 or nextPos_x >= m or nextPos_y < 0 or nextPos_y >= n:
                    continue
                if grid[nextPos_x][nextPos_y] == \"#\" or nextPos == boxPos:      # 易错点2: 遇到box的话也不能前进
                    continue
                if nextPos in visited:
                    continue
                heappush(hq, (step + abs(nextPos[0] - endPos[0]) + abs(nextPos[1] - endPos[1]), step + 1, nextPos))
                visited.add(nextPos)
                
        return False

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i, j)
                if grid[i][j] == \"B\":
                    box = (i, j)
                if grid[i][j] == \"S\":
                    person = (i, j)
                    
        def valid(x, y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] != \"#\"
        
        def check(curr, dest, box):
            queue = deque([curr])
            v = set()
            while queue:
                pos = queue.popleft()
                if pos == dest:
                    return True
                new_pos = [(1,0),(-1,0),(0,1),(0,-1)]
                for x, y in new_pos:
                    nx, ny = pos[0]+x, pos[1]+y
                    if valid(nx, ny) and (nx, ny) not in v and (nx, ny) != box:
                        v.add((nx, ny))
                        queue.append((nx, ny))
                        
            return False
        
        
        
        queue = deque([(0,box,person)])
        visited = {box+person}
        while queue:
            dist, box, person = queue.popleft()
            if box == target:
                return dist
            
            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            # b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            b_coord = [(1,0),(-1,0),(0,1),(0,-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]
            
            for new_box,new_person in zip(b_coord,p_coord):
                bx, by = box[0]+new_box[0], box[1]+new_box[1]
                if valid(bx, by) and box+new_box not in visited:
                    if valid(*new_person) and check(person,new_person,box):
                        visited.add((box+new_box))
                        queue.append((dist+1,(bx, by),box))
                        ###after shifting, the person's pos is old box's pos
        return -1
            
        
                    
                
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        
        def check(p1, p2, t1, t2, b1, b2):#g is new grid
            visited = visited = [[False for _ in range(n)] for _ in range(m)]
            queue = collections.deque()
            queue.append((p1, p2))
            visited[p1][p2] = True
            
            while queue:
                x, y = queue.popleft()
                if (x, y) == (t1, t2):
                    return True
                for dx, dy in moves:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m  and 0 <= ny < n:
                        if visited[nx][ny]: continue
                        if (nx, ny) == (t1, t2): return True
                        if (nx, ny) != (b1, b2) and grid[nx][ny] != '#':
                            queue.append((nx, ny))
                            visited[nx][ny] = True
            return False
        
        def inbound(x, y):
            return 0 <= x < m and 0 <= y < n
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] != '#':
                    if grid[i][j] == 'S':
                        player = (i, j)
                    elif grid[i][j] == 'B':
                        box = (i, j)
                    elif grid[i][j] == 'T':
                        end = (i, j)
        #player box end
        p1, p2 = player
        b1, b2 = box
        e1, e1 = end    
        
        visited = set()
        step = -1
        
        queue = collections.deque()
        queue.append((b1, b2, p1, p2))
        
        while queue:
            step += 1
            for _ in range(len(queue)):#别忘了是层序遍历！！！
                x, y, p1, p2 = queue.popleft()
                #up
                if inbound(x - 1, y) and inbound(x + 1, y) and grid[x + 1][y] != '#' and check(p1, p2, x + 1, y, x, y):
                    if (x - 1, y, x, y) not in visited:
                        if grid[x - 1][y] != '#':
                            if grid[x - 1][y] == 'T':
                                return step + 1
                            else:
                                queue.append((x - 1, y, x, y))
                                visited.add((x - 1, y, x, y))
                                visited.add((x, y, x + 1, y))
                #down
                if inbound(x - 1, y) and inbound(x + 1, y) and grid[x - 1][y] != '#' and check(p1, p2, x - 1, y, x, y):
                    if (x + 1, y, x, y) not in visited:
                        if grid[x + 1][y] != '#':
                            if grid[x + 1][y] == 'T':
                                return step + 1
                            else:
                                queue.append((x + 1, y, x, y))
                                visited.add((x + 1, y, x, y))
                                visited.add((x, y, x - 1, y))

                #left
                if inbound(x, y + 1) and inbound(x, y - 1) and grid[x][y + 1] != '#' and check(p1, p2, x, y + 1, x, y):
                    if (x, y - 1, x, y) not in visited:
                        if grid[x][y - 1] != '#':
                            if grid[x][y - 1] == 'T':
                                return step + 1
                            else:
                                queue.append((x, y - 1, x, y))
                                visited.add((x, y - 1, x, y))
                                visited.add((x, y, x, y + 1))

                #right
                if inbound(x, y + 1) and inbound(x, y - 1) and grid[x][y - 1] != '#' and check(p1, p2, x, y - 1, x, y):
                    if (x, y + 1, x, y) not in visited:
                        if grid[x][y + 1] != '#':
                            if grid[x][y + 1] == 'T':
                                return step + 1
                            else:
                                queue.append((x, y + 1, x, y))
                                visited.add((x, y + 1, x, y))
                                visited.add((x, y, x, y - 1))
        
        return -1

'''
Lets break the question into simple parts:

Lets think that we have no person and we have to find the minimum path between box and the target. Easy right? Simple BFS.

If you know how to solve the first part, what I actually do is modified first part with few constraints.

I just check whether the box can be shifted to the new position(up, down, left, right)
For it to be shifted to the new position the person has to be in a corresponding position right?
So we check if the person can travel from his old position to his corresponding new position(using another BFS).
If the person can travel to his new position than the box can be shifted, otherwise the box cannot be shifted.
We keep repeating step 2 until we reach the target or it is not possible to move the box anymore.

NOTE : If you know A* algorithm, you can use Euclidean distance as heuristic and use a priority queue instead of normal queue, the worst case time might increase but but average case will get better.
'''


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:

        # this loop is to get the coordinates of target, box and person. Nothing else is gained here
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i,j)
                if grid[i][j] == \"B\":
                    box = (i,j)
                if grid[i][j] == \"S\":
                    person = (i,j)

        # this function checks whether the given coordinates/indices are valid to go
        def valid(x,y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'

        # this function checks whether the person can travel from current postition to destination position.
        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.
        def check(curr,dest,box):
            que = deque([curr])
            v = set()
            while que:
                pos = que.popleft()
                if pos == dest: return True
                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]
                for x,y in new_pos:
                    if valid(x,y) and (x,y) not in v and (x,y)!=box:
                        v.add((x,y))
                        que.append((x,y))
            return False

        q = deque([(0,box,person)])
        vis = {box+person}
        # this is the main bfs which gives us the answer
        while q :
            dist, box, person = q.popleft()
            if box == target: # return the distance if box is at the target
                return dist

            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]

            for new_box,new_person in zip(b_coord,p_coord): 
                # we check if the new box coordinates are valid and our current state is not in vis
                if valid(*new_box) and new_box+box not in vis:
                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates
                    if valid(*new_person) and check(person,new_person,box):
                        vis.add(new_box+box)
                        q.append((dist+1,new_box,box))

        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
         # this loop is to get the coordinates of target, box and person. Nothing else is gained here
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i,j)
                if grid[i][j] == \"B\":
                    box = (i,j)
                if grid[i][j] == \"S\":
                    person = (i,j)

        # this function checks whether the given coordinates/indices are valid to go
        def valid(x,y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'

        # this function checks whether the person can travel from current postition to destination position.
        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.
        def check(curr,dest,box):
            que = deque([curr])
            v = set()
            while que:
                pos = que.popleft()
                if pos == dest: return True
                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]
                for x,y in new_pos:
                    if valid(x,y) and (x,y) not in v and (x,y)!=box:
                        v.add((x,y))
                        que.append((x,y))
            return False

        q = deque([(0,box,person)])
        vis = {box+person}
        # this is the main bfs which gives us the answer
        while q :
            dist, box, person = q.popleft()
            if box == target: # return the distance if box is at the target
                return dist

            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]

            for new_box,new_person in zip(b_coord,p_coord): 
                # we check if the new box coordinates are valid and our current state is not in vis
                if valid(*new_box) and new_box+box not in vis:
                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates
                    if valid(*new_person) and check(person,new_person,box):
                        vis.add(new_box+box)
                        q.append((dist+1,new_box,box))

        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dirs = [(0, 1), (-1, 0), (1, 0), (0, -1)]
        m, n = len(grid), len(grid[0])
        def connected(s, e):
            q = collections.deque([s])
            visited = set([s])
            while q:
                r, c = q.popleft()
                if (r, c) == e: return True
                for dr, dc in dirs:
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '.':
                        if (nr, nc) not in visited:
                            visited.add((nr, nc))
                            q.append((nr, nc))
            return False
        
        B = S = T = (0, 0)
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 'B': 
                    B = (r, c)
                    grid[r][c] = '.'
                elif grid[r][c] == 'S': 
                    S = (r, c)
                    grid[r][c] = '.'
                elif grid[r][c] == 'T': 
                    T = (r, c)
                    grid[r][c] = '.'
                    
        ans = 0
        q = collections.deque([(B, S, 0)])
        visited = set([(B, S)])
        while q:
            (r, c), (rs, cs), step = q.popleft()
            if (r, c) == T: return step
            for dr, dc in dirs:
                nr, nc = r+dr, c+dc
                pr, pc = r-dr, c-dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '.' and ((nr, nc), (r, c)) not in visited:
                    grid[r][c] = 'B'
                    if 0 <= pr < m and 0 <= pc < n and grid[pr][pc] == '.' and connected((pr, pc), (rs, cs)):
                        visited.add(((nr, nc), (r, c)))
                        q.append(((nr, nc), (r, c), step+1))
                    grid[r][c] = '.'
        return -1
                        
            
                    
            


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i, j)
                if grid[i][j] == \"B\":
                    box = (i, j)
                if grid[i][j] == \"S\":
                    person = (i, j)
                    
        def valid(x, y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] != \"#\"
        
        def check(curr, dest, box):
            queue = deque([curr])
            v = set()
            while queue:
                pos = queue.popleft()
                if pos == dest:
                    return True
                new_pos = [(1,0),(-1,0),(0,1),(0,-1)]
                for x, y in new_pos:
                    nx, ny = pos[0]+x, pos[1]+y
                    if valid(nx, ny) and (nx, ny) not in v and (nx, ny) != box:
                        v.add((nx, ny))
                        queue.append((nx, ny))
                        
            return False
        
        
        
        queue = deque([(0,box,person)])
        visited = {box+person}
        while queue:
            dist, box, person = queue.popleft()
            if box == target:
                return dist
            
            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            # b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            b_coord = [(1,0),(-1,0),(0,1),(0,-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            # p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]
            p_coord = [(-1,0),(1,0),(0,-1),(0,1)]
            
            for new_box,new_person in zip(b_coord,p_coord):
                bx, by = box[0]+new_box[0], box[1]+new_box[1]
                px, py = box[0]+new_person[0], box[1]+new_person[1]
                
                if valid(bx, by) and box+new_box not in visited:
                    if valid(px, py) and check(person,(px, py),box):
                        visited.add((box+new_box))
                        queue.append((dist+1,(bx, by),box))
                        ###after shifting, the person's pos is old box's pos
        return -1
            
        
                    
                
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def is_floor(i, j):
            return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] != '#'
        def bfs(start_i, start_j, box_i, box_j):
            visited, queue, reach_list = [[0 for _ in range(n)] for _ in range(m)], [(start_i, start_j)], []
            visited[start_i][start_j] = 1
            reach_list_upbound = len([1 for delta_i, delta_j in [(0, -1), (-1, 0), (0, 1), (1, 0)] if is_floor(box_i + delta_i, box_j + delta_j)])
            while queue:
                start_i, start_j = queue.pop(0)
                for delta_i, delta_j in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
                    if start_i + delta_i == box_i and start_j + delta_j == box_j:
                        reach_list.append((delta_i, delta_j))
                        if len(reach_list) >= reach_list_upbound:
                            return reach_list
                    elif is_floor(start_i + delta_i, start_j + delta_j) and visited[start_i + delta_i][start_j + delta_j] == 0:
                        visited[start_i + delta_i][start_j + delta_j] = 1
                        queue.append((start_i + delta_i, start_j + delta_j))
            return reach_list
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'S': source = (i, j)
                elif grid[i][j] == 'B': box = (i, j)
                elif grid[i][j] == 'T': target = (i, j)
        queue = [(source, box, 0)]
        visited = set()
        while queue:
            source, box, depth = queue.pop(0)
            if box[0] == target[0] and box[1] == target[1]: return depth
            reach_list = bfs(source[0], source[1], box[0], box[1])
            for mov in reach_list:
                s, b = (box[0], box[1]), (box[0] + mov[0], box[1] + mov[1])
                if is_floor(b[0], b[1]) and (s, b) not in visited:
                    visited.add((s, b))
                    queue.append((s, b, depth + 1))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        n = len(grid)
        m = len(grid[0])
        walls = set()
        for i in range(-1, n+1):
            for j in [-1,m]:
                walls.add(i + j *1j)
        for i in [-1,n]:
            for j in range(-1, m+1):
                walls.add(i + j *1j)

        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == \"S\":
                    spos = i + j * 1j
                elif c == \"T\":
                    tpos = i + j * 1j
                elif c == \"B\":
                    bpos = i + j * 1j
                elif c == \"#\":
                    walls.add(i + j * 1j)
        
        def children(node):
            return [node + x for x in [1,-1,1j,-1j]]
        
        def connected(pos1, pos2, bpos):
            q = [pos1]
            seen = set(q)
            while q:
                node = q.pop(0)
                if node == pos2: return True
                for child in children(node):
                    if child in walls or child == bpos: continue
                    if child in seen: continue
                    seen.add(child)
                    q.append(child)
            return False
        
        depth = {(spos, bpos): 0}
        
        q = [(spos, bpos)]
        while q:
            spos, bpos = q.pop(0)
            if bpos == tpos:
                return depth[(spos, bpos)]
            for child in children(bpos):
                if child in walls: continue
                newspos = 2*bpos - child
                if newspos in walls: continue
                if not connected(spos, newspos, bpos): continue
                if (newspos, child) in depth: continue
                depth[(newspos, child)] = depth[(spos, bpos)] + 1
                q.append((newspos, child))
        return -1


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m,n=len(grid),len(grid[0])
        dirs=[(0,1),(0,-1),(1,0),(-1,0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='S':
                    S=(i,j)
                if grid[i][j]=='B':
                    B=(i,j)
                if grid[i][j]=='T':
                    T=(i,j)
                    
                    
        def check(x,y):    #判断这个位置是否有效
            return 0<=x<m and 0<=y<n and grid[x][y]!='#'
                    
            
        def canmoveto(e,b,q,visit):          #判断人能否到达目标位置
            while q:
                p=q.pop(0)
                if p==e:
                    return True
                for dx,dy in dirs:
                    nx,ny=p[0]+dx,p[1]+dy
                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:
                        q.append((nx,ny))
                        visit.add((nx,ny))
            return False
        
        def move(e,q,visit):   #判断人能否把箱子推到目标位置
            res = 0
            while q:
                size=len(q)
                for _ in range(size):
                    b, p = q.pop(0)
                    if b == e:
                        return res
                    
                    for i, j in dirs:
                        nx, ny = b[0] + i, b[1] + j #
                        if check(nx, ny) and \\
                            check(b[0] - i, b[1] - j) and\\
                            ((nx, ny), b) not in visit and \\
                            canmoveto((b[0] - i, b[1] - j), b, [p], set([p])):
                            q.append(((nx, ny), b))
                            visit.add(((nx, ny), b))
                res += 1
            return -1
        return move(T,[(B,S)],set([(B,S)]))
                        
                
                
        
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        # where can player move next?
        def player_moves(box_i, box_j, p_i, p_j):
            res=[]
            if p_i > 0 and grid[p_i-1][p_j] != '#' and (p_i-1, p_j) != (box_i, box_j):
                res.append((p_i-1, p_j))
            if p_i < len(grid)-1 and grid[p_i+1][p_j] != '#' and (p_i+1, p_j) != (box_i, box_j):
                res.append((p_i+1, p_j))
            if p_j > 0 and grid[p_i][p_j-1] != '#' and (p_i, p_j-1) != (box_i, box_j):
                res.append((p_i, p_j-1))    
            if p_j < len(grid[0])-1 and grid[p_i][p_j+1] != '#' and (p_i, p_j+1) != (box_i, box_j):
                res.append((p_i, p_j+1))
            return res

        # Can player walk to this cell?            
        def is_accessible(cell_i, cell_j, box_i, box_j, p_i, p_j):
            if grid[cell_i][cell_j]=='#':
                return False
            q=deque()
            visited=set()
            q.append((p_i, p_j))
            visited.add((p_i, p_j))
            while q:
                size=len(q)
                for i in range(size):
                    pop=q.popleft()
                    if pop==(cell_i,cell_j):
                        return True
                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):
                        if nex not in visited:
                            q.append(nex)
                            visited.add(nex)
            return False 
            
        # each state is defined by box location and player location
        def box_moves(state):
            res=set()
            box_i, box_j, p_i, p_j = state[0], state[1], state[2], state[3]
            # first check box's four neighbor if empty floor cell, and accessible to player, the cell of opposite direction should also be empty. Then moves, update box & player location
            if box_i>0 and is_accessible(box_i-1, box_j, box_i, box_j, p_i, p_j) and box_i+1<len(grid) and grid[box_i+1][box_j]!='#':  # push down, player replace box location
                res.add((box_i+1, box_j, box_i, box_j))
            if box_i<len(grid)-1 and is_accessible(box_i+1, box_j, box_i, box_j, p_i, p_j) and box_i-1>=0 and grid[box_i-1][box_j]!='#':   # push up
                res.add((box_i-1, box_j, box_i, box_j))
            if box_j>0 and is_accessible(box_i, box_j-1, box_i, box_j, p_i, p_j) and box_j+1<len(grid[0]) and grid[box_i][box_j+1]!='#':  # push right
                res.add((box_i, box_j+1, box_i, box_j))
            if box_j<len(grid[0])-1 and is_accessible(box_i, box_j+1, box_i, box_j, p_i, p_j) and box_j-1>=0 and grid[box_i][box_j-1]!='#':  # push left
                res.add((box_i, box_j-1, box_i, box_j))
            return res
            
        def start_state():
            box_i, box_j, p_i, p_j = -1, -1, -1, -1
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]=='B':
                        box_i, box_j = i, j
                    elif grid[i][j]=='S':
                        p_i, p_j = i, j
            return (box_i, box_j, p_i, p_j)
                
        q=deque()
        visited=set()
        start=start_state()
        q.append(start)
        visited.add(start)
        moves=-1
        while q:
            size=len(q)
            moves +=1
            for i in range(size):
                pop=q.popleft()
                if grid[pop[0]][pop[1]]=='T':
                    return moves
                for nx in box_moves(pop):                    
                    if nx not in visited:
                        q.append(nx)
                        visited.add(nx)
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        R, C = len(grid), len(grid[0])
        b_pos = s_pos = t_pos = None
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'B':
                    b_pos = (r, c)
                if grid[r][c] == 'S':
                    s_pos = (r, c)
                if grid[r][c] == 'T':
                    t_pos = (r, c)
        def is_empty(r, c):
            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'
        @lru_cache(None)
        def can_reach(r1, c1, r2, c2, br, bc):
            if not is_empty(r2, c2):
                return False
            q = [(r1, c1)]
            used = set()
            for r, c in q:
                if (r, c) in used or (r, c) == (br, bc):
                    continue
                used.add((r, c))
                if (r, c) == (r2, c2):
                    return True
                for dr, dc in dirs:
                    nr, nc = dr + r, dc + c
                    if is_empty(nr, nc):
                        q.append((nr, nc))
            return False
        #print(f\"b_pos {b_pos}, t_pos {t_pos}\")
        visited = set()
        pq = [(0, b_pos, s_pos)]
        while pq:
            #print(f\"pq {pq}\")
            steps, b_pos, s_pos = heappop(pq)
            if (b_pos, s_pos) in visited:
                continue
            visited.add((b_pos, s_pos))
            if b_pos == t_pos:
                return steps
            sr, sc = s_pos
            br, bc = b_pos
            for dr, dc in dirs:
                br1, bc1 = br + dr, bc + dc
                br2, bc2 = br - dr, bc - dc
                #print(f\"(br1, bc1) {br1, bc1}, (br2, bc2) {br2, bc2}\")
                if is_empty(br2, bc2) and can_reach(sr, sc, br1, bc1, br, bc):
                    heappush(pq, (steps + 1, (br2, bc2), b_pos))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        R, C = len(grid), len(grid[0])
        b_pos = s_pos = t_pos = None
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'B':
                    b_pos = (r, c)
                if grid[r][c] == 'S':
                    s_pos = (r, c)
                if grid[r][c] == 'T':
                    t_pos = (r, c)
        def is_empty(r, c):
            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'

        def can_reach(r1, c1, r2, c2, br, bc):
            if not is_empty(r2, c2):
                return False
            q = [(r1, c1)]
            used = set()
            for r, c in q:
                if (r, c) in used or (r, c) == (br, bc):
                    continue
                used.add((r, c))
                if (r, c) == (r2, c2):
                    return True
                for dr, dc in dirs:
                    nr, nc = dr + r, dc + c
                    if is_empty(nr, nc):
                        q.append((nr, nc))
            return False
        #print(f\"b_pos {b_pos}, t_pos {t_pos}\")
        visited = set()
        pq = [(0, b_pos, s_pos)]
        while pq:
            #print(f\"pq {pq}\")
            steps, b_pos, s_pos = heappop(pq)
            if (b_pos, s_pos) in visited:
                continue
            visited.add((b_pos, s_pos))
            if b_pos == t_pos:
                return steps
            sr, sc = s_pos
            br, bc = b_pos
            for dr, dc in dirs:
                br1, bc1 = br + dr, bc + dc
                br2, bc2 = br - dr, bc - dc
                #print(f\"(br1, bc1) {br1, bc1}, (br2, bc2) {br2, bc2}\")
                if is_empty(br2, bc2) and can_reach(sr, sc, br1, bc1, br, bc):
                    heappush(pq, (steps + 1, (br2, bc2), b_pos))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        def player_moves(box_i, box_j, player_i, player_j):
            res=[]
            if player_i > 0 and grid[player_i-1][player_j] != '#' and (player_i-1, player_j) != (box_i, box_j):
                res.append((player_i-1, player_j))
            if player_i < len(grid)-1 and grid[player_i+1][player_j] != '#' and (player_i+1, player_j) != (box_i, box_j):
                res.append((player_i+1, player_j))
            if player_j > 0 and grid[player_i][player_j-1] != '#' and (player_i, player_j-1) != (box_i, box_j):
                res.append((player_i, player_j-1))    
            if player_j < len(grid[0])-1 and grid[player_i][player_j+1] != '#' and (player_i, player_j+1) != (box_i, box_j):
                res.append((player_i, player_j+1))
            return res
                    
        def can_player_access_cell(cell_i, cell_j, box_i, box_j, player_i, player_j):
            if grid[cell_i][cell_j]=='#':
                return False
            q=deque()
            visited=set()
            q.append((player_i, player_j))
            visited.add((player_i, player_j))
            while q:
                size=len(q)
                for i in range(size):
                    pop=q.popleft()
                    if pop==(cell_i,cell_j):
                        return True
                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):
                        if nex not in visited:
                            q.append(nex)
                            visited.add(nex)
            return False 
            
        def box_moves(state):
            res=set()
            print(('state', state))
            box_i, box_j, player_i, player_j = state[0], state[1], state[2], state[3]
            print(('box_i',box_i))
            # first check box's four neighbor if empty floor cell, and accessible to player, the cell of opposite direction should also be empty# moves, update box location, mark B, update player location
            if box_i>0 and can_player_access_cell(box_i-1, box_j, box_i, box_j, player_i, player_j) and box_i+1<len(grid) and grid[box_i+1][box_j]!='#':  # push down, player replace box location
                res.add((box_i+1, box_j, box_i, box_j))
            if box_i<len(grid)-1 and can_player_access_cell(box_i+1, box_j, box_i, box_j, player_i, player_j) and box_i-1>=0 and grid[box_i-1][box_j]!='#':   # push up
                res.add((box_i-1, box_j, box_i, box_j))
            if box_j>0 and can_player_access_cell(box_i, box_j-1, box_i, box_j, player_i, player_j) and box_j+1<len(grid[0]) and grid[box_i][box_j+1]!='#':  # push right
                res.add((box_i, box_j+1, box_i, box_j))
            if box_j<len(grid[0])-1 and can_player_access_cell(box_i, box_j+1, box_i, box_j, player_i, player_j) and box_j-1>=0 and grid[box_i][box_j-1]!='#':  # push left
                res.add((box_i, box_j-1, box_i, box_j))
            print(('res', res))
            return res
            
            
        def start_state():
            box_i, box_j, player_i, player_j = -1, -1, -1, -1
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]=='B':
                        box_i, box_j = i, j
                    elif grid[i][j]=='S':
                        player_i, player_j = i, j
            return (box_i, box_j, player_i, player_j)
                
        q=deque()
        visited=set()
        start=start_state()
        q.append(start)
        visited.add(start)
        moves=-1
        while q:
            size=len(q)
            print(size)
            print(q)
            moves +=1
            
            for i in range(size):
                pop=q.popleft()
                print(('pop', pop))
                if grid[pop[0]][pop[1]]=='T':
                    return moves
                    
                for nx in box_moves(pop):
                    print(('nx',nx))
                    
                    if nx not in visited:
                        q.append(nx)
                        visited.add(nx)
                    
        return -1
        
                
                
                
                


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        M, N = len(grid), len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j] in ['#', '.']:
                    continue
                if grid[i][j] == 'S':
                    player = (i, j)
                elif grid[i][j] == 'B':
                    box = (i, j)
                else:
                    target = (i, j)

        def heuristic(box):
            return abs(target[0] - box[0]) + abs(target[1] - box[1])

        @functools.lru_cache(None)
        def reach(player, pos, box):
            i, j = pos
            if not (0 <= i < M and 0 <= j < N and grid[i][j] != '#'):
                return False
            hp = [player]
            seen = set([player])
            while hp:
                player = heapq.heappop(hp)
                if player == pos:
                    return True
                p0, p1 = player
                for i, j in [(p0 - 1, p1), (p0 + 1, p1), (p0, p1 - 1), (p0, p1 + 1)]:
                    if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and (i, j) != box and (i, j) not in seen:
                        seen.add((i, j))
                        heapq.heappush(hp, (i, j))
            return False

        seen = set([(box, player)])
        hp = [(heuristic(box), 0, box, player)]
        while hp:
            _, step, box, player = heapq.heappop(hp)
            print(box)
            if box == target:
                return step
            b0, b1 = box
            for i, j in [(b0 - 1, b1), (b0 + 1, b1), (b0, b1 - 1), (b0, b1 + 1)]:
                if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and ((i, j), player) not in seen and reach(player, (
                b0 * 2 - i, b1 * 2 - j), box):
                    seen.add(((i, j), player))
                    heapq.heappush(hp, (heuristic((i, j)) + step + 1, step + 1, (i, j), box))
        return -1
                    
                
                
                
                
                
                
                
                
                


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid[0])
        # two source bfs
        def neighbor(r, c):
            for nr, nc in [[r+1, c], [r, c+1], [r-1,c], [r,c-1]]:
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
                    yield nr,  nc
                    
        def can_reach(worker, target, box):
            if worker == target:
                return True
            if target[0] >= R or target[0] < 0 or target[1] >= C or target[1] < 0 or grid[target[0]][target[1]] == '#':
                return False
            
            start = [worker]
            end = [target]
            start_seen = {worker}
            end_seen = {target}
            
            while start and end:
                n_start = []
                for node in start:
                    r, c = node
                    for nr, nc in neighbor(r, c):
                        if (nr, nc) in end_seen:
                            return True
                        if (nr, nc) != box and (nr, nc) not in start_seen:
                            start_seen.add((nr, nc))
                            n_start.append((nr, nc))
                n_end = []
                for node in end:
                    r, c = node
                    for nr, nc in neighbor(r, c):
                        if (nr, nc) in start_seen:
                            return True
                        if (nr, nc) != box and (nr, nc) not in end_seen:
                            end_seen.add((nr, nc))
                            n_end.append((nr, nc))
                start = n_start
                end = n_end
        
        S, B, T = None, None, None
        
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'S':
                    S = (r, c)
                elif grid[r][c] == 'B':
                    B = (r, c)
                elif grid[r][c] == 'T':
                    T = (r, c)
                    
        level = [(S, B)]
        seen = {(S, B)}
        steps = 0
        while level:
            n_level = []
            for player, box in level:
                r, c = box
                for nr, nc in neighbor(r, c):
                    opp_r, opp_c = 2 * r - nr, 2 * c - nc
                    if can_reach(player, (opp_r, opp_c), box):
                        if (nr, nc) == T:
                            return steps + 1
                        n_state = (box, (nr, nc))
                        if n_state not in seen:
                            seen.add(n_state)
                            n_level.append(n_state)
            
            level = n_level
            # print(seen, level)
            steps += 1
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        def player_moves(box_i, box_j, player_i, player_j):
            res=[]
            if player_i > 0 and grid[player_i-1][player_j] != '#' and (player_i-1, player_j) != (box_i, box_j):
                res.append((player_i-1, player_j))
            if player_i < len(grid)-1 and grid[player_i+1][player_j] != '#' and (player_i+1, player_j) != (box_i, box_j):
                res.append((player_i+1, player_j))
            if player_j > 0 and grid[player_i][player_j-1] != '#' and (player_i, player_j-1) != (box_i, box_j):
                res.append((player_i, player_j-1))    
            if player_j < len(grid[0])-1 and grid[player_i][player_j+1] != '#' and (player_i, player_j+1) != (box_i, box_j):
                res.append((player_i, player_j+1))
            return res
                    
        def can_player_access_cell(cell_i, cell_j, box_i, box_j, player_i, player_j):
            if grid[cell_i][cell_j]=='#':
                return False
            qu=deque()
            visited=set()
            qu.append((player_i, player_j))
            visited.add((player_i, player_j))
            while qu:
                size=len(qu)
                for i in range(size):
                    pop=qu.popleft()
                    if pop==(cell_i,cell_j):
                        return True
                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):
                        if nex not in visited:
                            qu.append(nex)
                            visited.add(nex)
            return False 
            
        def box_moves(state):
            res=set()
            print(('state', state))
            box_i, box_j, player_i, player_j = state[0], state[1], state[2], state[3]
            print(('box_i',box_i))
            # first check box's four neighbor if empty floor cell, and accessible to player, the cell of opposite direction should also be empty# moves, update box location, mark B, update player location
            if box_i>0 and can_player_access_cell(box_i-1, box_j, box_i, box_j, player_i, player_j) and box_i+1<len(grid) and grid[box_i+1][box_j]!='#':  # push down, player replace box location
                res.add((box_i+1, box_j, box_i, box_j))
            if box_i<len(grid)-1 and can_player_access_cell(box_i+1, box_j, box_i, box_j, player_i, player_j) and box_i-1>=0 and grid[box_i-1][box_j]!='#':   # push up
                res.add((box_i-1, box_j, box_i, box_j))
            if box_j>0 and can_player_access_cell(box_i, box_j-1, box_i, box_j, player_i, player_j) and box_j+1<len(grid[0]) and grid[box_i][box_j+1]!='#':  # push right
                res.add((box_i, box_j+1, box_i, box_j))
            if box_j<len(grid[0])-1 and can_player_access_cell(box_i, box_j+1, box_i, box_j, player_i, player_j) and box_j-1>=0 and grid[box_i][box_j-1]!='#':  # push left
                res.add((box_i, box_j-1, box_i, box_j))
            print(('res', res))
            return res
            
            
        def start_state():
            box_i, box_j, player_i, player_j = -1, -1, -1, -1
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]=='B':
                        box_i, box_j = i, j
                    elif grid[i][j]=='S':
                        player_i, player_j = i, j
            return (box_i, box_j, player_i, player_j)
                
        q=deque()
        visited=set()
        start=start_state()
        q.append(start)
        visited.add(start)
        moves=-1
        #return
        while q:
            size=len(q)
            print(size)
            print(q)
            moves +=1
            
            for i in range(size):
                pop=q.popleft()
                print(('pop', pop))
                if grid[pop[0]][pop[1]]=='T':
                    return moves
                    
                for nx in box_moves(pop):
                    print(('nx',nx))
                    
                    if nx not in visited:
                        q.append(nx)
                        visited.add(nx)
                    
        return -1
        
                
                
                
                


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    bi, bj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    si, sj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    ti, tj = i, j
                    grid[i][j] = '.'
        q = [(bi, bj, si, sj, 0)]
        seen = {(bi, bj, si, sj)}
        while q:
            bi, bj, si, sj, dist = q.pop(0)
            if (bi, bj) == (ti, tj):
                return dist
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                si_new, sj_new = bi+dx, bj+dy
                bi_new, bj_new = bi-dx, bj-dy
                if (bi_new, bj_new, bi, bj) not in seen and self.canMoveTo(grid, bi, bj, si, sj, si_new, sj_new) and 0 <= bi_new < m and 0 <= bj_new < n and grid[bi_new][bj_new] == '.':
                    q.append((bi_new, bj_new, bi, bj, dist+1))
                    seen.add((bi_new, bj_new, bi, bj))
        return -1
    
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            if si == si_new and sj == sj_new:
                return True
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return False
    '''
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):
        m, n = len(grid), len(grid[0])
        if si == si_new and sj == sj_new:
            return True
        visited.add((si, sj))
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#' and self.canMoveTo(grid, bi, bj, i, j, si_new, sj_new, visited):
                return True
        return False
        
    def canMoveTo(self, grid, bi, bj, si, sj, validSet):
        m, n = len(grid), len(grid[0])
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) in validSet:
                continue
            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                validSet.add((i, j))
                self.canMoveTo(grid, bi, bj, i, j, validSet)
        return validSet
    '''    

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        cache = {}
        visited = set()
        def dp(b, p):
            if not (0<=b[0]<m and 0<=b[1]<n and 0<=p[0]<m and 0<=p[1]<n) or grid[b[0]][b[1]] == '#' or grid[p[0]][p[1]] == '#' or b == p:
                return float(\"inf\")
            if grid[b[0]][b[1]] == 'T':
                return 0
            if (b, p) in cache:
                return cache[(b, p)]
            if (b, p) in visited:
                return float(\"inf\")
            visited.add((b, p))
            ans = float(\"inf\")
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)
            ans = min(ans, min(dp(b, pp) for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1))))
            visited.remove((b, p))
            cache[(b, p)] = ans
            return ans
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
        ans = dp(b, p)
        print(cache)
        return -1 if ans == float(\"inf\") else ans
    
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        q = collections.deque()
        visited = set()
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
                    
        q.append((b, p, 0))
        visited.add((b, p))
        while q:
            b, p, c = q.popleft()
            if grid[b[0]][b[1]] == 'T':
                return c
            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):
                if (b, pp) not in visited and 0<=pp[0]<m and 0<=pp[1]<n and grid[pp[0]][pp[1]] != '#' and b != pp:
                    q.appendleft((b, pp, c))
                    visited.add((b, pp))
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                p = b
                b = (b[0]+delta[0], b[1]+delta[1])
                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':
                    q.append((b, p, c+1))
                    visited.add((b, p))
        return -1
            
            

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    bi, bj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    si, sj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    ti, tj = i, j
                    grid[i][j] = '.'
        q = [(bi, bj, si, sj, 0)]
        seen = {(bi, bj, si, sj)}
        while q:
            bi, bj, si, sj, dist = q.pop(0)
            if (bi, bj) == (ti, tj):
                return dist
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                si_new, sj_new = bi+dx, bj+dy
                bi_new, bj_new = bi-dx, bj-dy
                if (bi_new, bj_new, bi, bj) not in seen and self.canMoveTo(grid, bi, bj, si, sj, si_new, sj_new) and 0 <= bi_new < m and 0 <= bj_new < n and grid[bi_new][bj_new] == '.':
                    q.append((bi_new, bj_new, bi, bj, dist+1))
                    seen.add((bi_new, bj_new, bi, bj))
        return -1
    
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            if si == si_new and sj == sj_new:
                return True
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return False
    '''
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):
        m, n = len(grid), len(grid[0])
        if si == si_new and sj == sj_new:
            return True
        visited.add((si, sj))
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#' and self.canMoveTo(grid, bi, bj, i, j, si_new, sj_new, visited):
                return True
        return False

    def canMoveTo(self, grid, bi, bj, si, sj, validSet):
        m, n = len(grid), len(grid[0])
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) in validSet:
                continue
            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                validSet.add((i, j))
                self.canMoveTo(grid, bi, bj, i, j, validSet)
        return validSet
    '''    

class Solution:
    def minPushBox(self, A: List[List[str]]) -> int:
        if not A: return -1

        rows, cols = len(A), len(A[0])
        box = end = dude = None
        
        for row in range(rows):
            for col in range(cols):
                if A[row][col] == 'B':   box = (row, col)
                elif A[row][col] == 'T': end = (row, col)
                elif A[row][col] == 'S': npc = (row, col)  
        
        def bfs(start, end, blocked):
            cache, q = set(start), collections.deque([start])
            while q:
                i, j = q.popleft()
                if (i, j) == end:
                    return True
                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    row, col = i + di, j + dj
                    if 0 <= row < rows and 0 <= col < cols and \\
                       (row, col) not in cache and A[row][col] != '#' and \\
                       (row, col) != blocked:
                        q.append((row, col))
                        cache.add((row, col))
            return False
                
        visited, q = set([(box, npc)]), collections.deque([(box, npc, 0)])
        while q:
            (i, j), player, moves = q.popleft()
            if (i, j) == end:
                return moves
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                row, col = i + di, j + dj
                if 0 <= row < rows and 0 <= col < cols and ((row, col), (i, j)) not in visited and A[row][col] != '#':
                    if bfs(player, (i - di, j - dj), (i, j)):
                        q.append(((row, col), (i, j), moves + 1))
                        visited.add(((row, col), (i, j)))
        return -1
                    

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        self.empty = [['.' for _ in range(n)] for _ in range(m)]
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == 'B': start = (i,j)
                if c == 'S': player = (i,j)
                if c == 'T': target = (i,j)
                if c == '#': self.empty[i][j] = '#'
        visit = [[0 for _ in range(n)] for _ in range(m)]
        visit[start[0]][start[1]] += 1
        deq = collections.deque([(start,player,(-1,-1))])
        push = 0
        paths = dict()
        while deq and push < m * n:
            sz = len(deq)
            for i in range(sz):
                box,player, previous = deq.popleft()
                if box == target: return push
                cango = paths[(player,box)] if (player,box) in paths else self.player(player, box,self.empty)
                paths[(player,box)] = cango
                for d in self.direction:
                    nr, nc = box[0] + d[0], box[1] + d[1]
                    pr,pc = box[0] + d[2], box[1] + d[3]
                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:
                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:
                            visit[nr][nc] +=1
                            deq.append(((nr,nc),(pr,pc),box))
            push += 1
        return -1
    
    def player(self, player, box, grid):
        m, n = len(grid), len(grid[0])
        visit = [[False for _ in range(n)] for _ in range(m)]
        visit[player[0]][player[1]] = True
        deq = collections.deque([player])
        while deq:
            sz = len(deq)
            for i in range(sz):
                cur = deq.popleft()
                for d in self.direction:
                    nr, nc = cur[0] + d[0], cur[1] + d[1]
                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):
                        visit[nr][nc] = True
                        deq.append((nr,nc))
        return visit
    
    def __init__(self):
        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))
        self.empty = None

class Solution:
    def minPushBox(self, A: List[List[str]]) -> int:
        if not A: return -1

        rows, cols = len(A), len(A[0])
        box = end = dude = None
        
        for row in range(rows):
            for col in range(cols):
                if A[row][col] == 'B':   box = (row, col)
                elif A[row][col] == 'T': end = (row, col)
                elif A[row][col] == 'S': npc = (row, col)  
        
        def bfs(start, end, blocked):
            cache, q = set(start), collections.deque([start])
            while q:
                i, j = q.popleft()
                if (i, j) == end:
                    return True
                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    row, col = i + di, j + dj
                    if 0 <= row < rows and 0 <= col < cols and \\
                       (row, col) not in cache and A[row][col] != '#' and \\
                       (row, col) != blocked:
                        q.append((row, col))
                        cache.add((row, col))
            return False
                
        visited, q = set([(box, npc)]), collections.deque([(box, npc, 0)])
        while q:
            (i, j), player, moves = q.popleft()
            if (i, j) == end:
                return moves
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                row, col = i + di, j + dj
                if 0 <= row < rows and 0 <= col < cols and ((row, col), (i, j)) not in visited and A[row][col] != '#':
                    if bfs(player, (i - di, j - dj), (i, j)):
                        q.append(((row, col), (i, j), moves + 1))
                        visited.add(((row, col), (i, j)))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        ## from https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/bfsbfs-by-haitao-yu/
        ## 双 BFS
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        M = len(grid)
        N = len(grid[0])
    
        def find_target(target):
            row,col = None, None
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == target:
                        row, col = i,j
                        break
            return row, col
        
        def check_pos_valid(i,j):
            if i >=0 and i < M and j >= 0 and j < N and grid[i][j] in [\"T\",\".\"]:
                return True
            else :
                return False
    
        def player_bfs(player_x,player_y, behind_box_x,behind_box_y):
            
            queue = [(player_x,player_y)]
            visited = set()
    
            while len(queue) !=0:
                player_x,player_y = queue.pop(0)
                visited.add((player_x,player_y))
                
                if (player_x,player_y) == (behind_box_x,behind_box_y):
                    return True
                
                for dx,dy in directions:
                    next_x = player_x + dx
                    next_y = player_y + dy
                    if check_pos_valid(next_x, next_y) and (next_x, next_y) not in visited:
                        queue.append( (next_x, next_y) )
                        visited.add( (next_x, next_y) )
            return False
    
    
    
        box_x,box_y = find_target(\"B\")
        player_x,player_y = find_target(\"S\")
        end_x, end_y = find_target(\"T\")
        init_state = (box_x,box_y, player_x,player_y,0)
        queue = [init_state]
        visited = set()
        visited.add((box_x,box_y, player_x,player_y))
    
        ## 清除 B 和 S
        grid[box_x][box_y] = \".\"
        grid[player_x][player_y] = \".\"
    
    
        # ## BFS #1
        while len(queue) !=0 :
            # print(queue)
            box_x,box_y, player_x,player_y, step  = queue.pop(0)
            # visited.add((box_x,box_y, player_x,player_y))  将时
            
            ## 检查箱子状态
            if (box_x, box_y) == (end_x, end_y):
                return step
            
            ## 更新箱子的位置
            grid[box_x][box_y] = \"B\"  ## B 是可以挡路的，导致 player 无法绕到箱子后。在对 player bfs 时需要考虑，因此置之为 B
            for dx,dy in directions:
                ## 箱子的下一个可能的位置
                box_next_x = box_x + dx
                box_next_y = box_y + dy
                if check_pos_valid(box_next_x, box_next_y):
                    ## 如果箱子的下一个可能位置合法，则检查当前箱子的后方位置是否合法（合法的话，箱子才可能移动到下一个位置）
                    behind_box_x = box_x - dx
                    behind_box_y = box_y - dy
                    if check_pos_valid(behind_box_x, behind_box_y):
                        ## 后方位置也合法，检查 player 是否能走到该位置(可以使用 bfs)
                        if player_bfs(player_x,player_y, behind_box_x,behind_box_y):
                            ## 如果可以走到，且当前位置未访问，则加入队列
                            next_state = (box_next_x, box_next_y, behind_box_x, behind_box_y, step+1)
                            if (box_next_x, box_next_y, behind_box_x, behind_box_y) not in visited:
                                queue.append(next_state)
                                visited.add((box_next_x, box_next_y, behind_box_x, behind_box_y))
            grid[box_x][box_y] = \".\"
        return -1   

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        ## from https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/bfsbfs-by-haitao-yu/
        ## 双 BFS
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        M = len(grid)
        N = len(grid[0])
    
        def find_target(target):
            row,col = None, None
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == target:
                        row, col = i,j
                        break
            return row, col
        
        def check_pos_valid(i,j):
            if i >=0 and i < M and j >= 0 and j < N and grid[i][j] in [\"T\",\".\"]:
                return True
            else :
                return False
    
        def player_bfs(player_x,player_y, behind_box_x,behind_box_y):
            
            queue = [(player_x,player_y)]
            visited = set()
    
            while len(queue) !=0:
                player_x,player_y = queue.pop(0)
                visited.add((player_x,player_y))
                
                if (player_x,player_y) == (behind_box_x,behind_box_y):
                    return True
                
                for dx,dy in directions:
                    next_x = player_x + dx
                    next_y = player_y + dy
                    if check_pos_valid(next_x, next_y) and (next_x, next_y) not in visited:
                        queue.append( (next_x, next_y) )
                        visited.add( (next_x, next_y) )
            return False
    
    
    
        box_x,box_y = find_target(\"B\")
        player_x,player_y = find_target(\"S\")
        end_x, end_y = find_target(\"T\")
        init_state = (box_x,box_y, player_x,player_y,0)
        queue = [init_state]
        visited = set()
        visited.add((box_x,box_y, player_x,player_y))
    
        ## 清除 B 和 S
        grid[box_x][box_y] = \".\"
        grid[player_x][player_y] = \".\"
    
    
        # ## BFS #1
        while len(queue) !=0 :
            # print(queue)
            box_x,box_y, player_x,player_y, step  = queue.pop(0)
            
            ## 检查箱子状态
            if (box_x, box_y) == (end_x, end_y):
                return step
            
            ## 更新箱子的位置
            grid[box_x][box_y] = \"B\"  ## B 是可以挡路的，导致 player 无法绕到箱子后。在对 player bfs 时需要考虑，因此置之为 B
            for dx,dy in directions:
                ## 箱子的下一个可能的位置
                box_next_x = box_x + dx
                box_next_y = box_y + dy
                if check_pos_valid(box_next_x, box_next_y):
                    ## 如果箱子的下一个可能位置合法，则检查当前箱子的后方位置是否合法（合法的话，箱子才可能移动到下一个位置）
                    behind_box_x = box_x - dx
                    behind_box_y = box_y - dy
                    if check_pos_valid(behind_box_x, behind_box_y):
                        ## 后方位置也合法，检查 player 是否能走到该位置(可以使用 bfs)
                        if player_bfs(player_x,player_y, behind_box_x,behind_box_y):
                            ## 如果可以走到，且当前位置未访问，则加入队列
                            next_state = (box_next_x, box_next_y, behind_box_x, behind_box_y, step+1)
                            if (box_next_x, box_next_y, behind_box_x, behind_box_y) not in visited:
                                queue.append(next_state)
                                visited.add((box_next_x, box_next_y, behind_box_x, behind_box_y))
            grid[box_x][box_y] = \".\"
        return -1   

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid[0])
        
        def nxt(pos):
            r, c = pos
            res = []
            for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
                    res.append((nr, nc))
            return res
        
        def connected(p, q, box):
            queue = collections.deque([p])
            seen = set()
            while queue:
                node = queue.popleft()
                for nr, nc in nxt(node):
                    if (nr, nc) != box:
                        if (nr, nc) == q:
                            return True
                        if (nr, nc) not in seen:
                            seen.add((nr, nc))
                            queue.append((nr, nc))
            return False
                
        target, box, worker = None, None, None
        
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'S':
                    worker = (r, c)
                if grid[r][c] == 'B':
                    box = (r, c)
                if grid[r][c] == 'T':
                    target = (r, c)
        
        level = []
        seen = set()
        for pos in nxt(box):
            #print(pos)
            if connected(pos, worker, box):
                level.append((box, pos))
                seen.add((box, pos))
                
        grid[box[0]][box[1]] = '.'
        steps = 0
        
        while level:
            n_level = []
            for b, w in level:
                candi = nxt(b)
                for pos in candi:
                    nb = (2 * b[0] - pos[0], 2 * b[1] - pos[1])
                    if nb == target:
                        return steps + 1
                    if nb in candi and (nb, b) not in seen and connected(w, pos, b):
                        seen.add((nb, b))
                        n_level.append((nb, b))
            steps += 1
            level = n_level
        
        return -1


class Solution:
    # DFS failed
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        cache = {}
        visited = set()
        def dp(b, p):
            if not (0<=b[0]<m and 0<=b[1]<n and 0<=p[0]<m and 0<=p[1]<n) or grid[b[0]][b[1]] == '#' or grid[p[0]][p[1]] == '#' or b == p:
                return float(\"inf\")
            if grid[b[0]][b[1]] == 'T':
                return 0
            if (b, p) in cache:
                return cache[(b, p)]
            if (b, p) in visited:
                return float(\"inf\")
            visited.add((b, p))
            ans = float(\"inf\")
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)
            ans = min(ans, min(dp(b, pp) for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1))))
            visited.remove((b, p))
            cache[(b, p)] = ans
            return ans
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
        ans = dp(b, p)
        print(cache)
        return -1 if ans == float(\"inf\") else ans
    
    # BFS
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        q = collections.deque()
        visited = set()
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
                    
        q.append((b, p, 0))
        visited.add((b, p))
        while q:
            b, p, c = q.popleft()
            if grid[b[0]][b[1]] == 'T':
                return c
            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):
                if (b, pp) not in visited and 0<=pp[0]<m and 0<=pp[1]<n and grid[pp[0]][pp[1]] != '#' and b != pp:
                    q.appendleft((b, pp, c))
                    visited.add((b, pp))
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                p = b
                b = (b[0]+delta[0], b[1]+delta[1])
                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':
                    q.append((b, p, c+1))
                    visited.add((b, p))
        return -1
            
            

class Solution:
    def minPushBox(self, grid) -> int:
        T = B = S = (-1, -1)
        l = len(grid)
        w = len(grid[0])
        for i in range(l):
            for j in range(w):
                if grid[i][j] == 'T':
                    T = (i, j)
                elif grid[i][j] == 'B':
                    B = (i, j)
                elif grid[i][j] == 'S':
                    S = (i, j)

        directions = [0, -1, 0, 1, 0]
        q = [B + S]
        visited = set()
        steps = 0
        self.next_step = (-1, -1, -1, -1)

        def is_pushable(cur_bs, dx, dy):
            bx, by, sx, sy = cur_bs
            nbx = bx + dx
            nby = by + dy
            nsx = bx - dx
            nsy = by - dy
            if is_valid(nbx, nby) and is_valid(nsx, nsy):
                if is_reachable(sx, sy, nsx, nsy, bx, by):
                    self.next_step = (nbx, nby, nsx, nsy)
                    return True
            return False

        def is_valid(nx, ny):
            return 0 <= nx < l and 0 <= ny < w and grid[nx][ny] != '#'

        def is_reachable(sx, sy, nsx, nsy, cur_bx, cur_by):
            queue = [(sx, sy)]
            visited_set = set()
            while queue:
                cur_s = queue.pop(0)
                if cur_s not in visited_set and cur_s != (cur_bx, cur_by):
                    visited_set.add(cur_s)
                    if cur_s == (nsx, nsy):
                        return True
                    cx, cy = cur_s
                    for idx in range(4):
                        dx, dy = directions[idx], directions[idx + 1]
                        nx, ny = cx + dx, cy + dy
                        if is_valid(nx, ny):
                            queue.append((nx, ny))
            return False

        while q:
            tmp = []
            for cur in q:
                if cur not in visited:
                    visited.add(cur)
                    for i in range(4):
                        dir_x, dir_y = directions[i], directions[i + 1]
                        if is_pushable(cur, dir_x, dir_y):
                            box_x, box_y, _, _ = self.next_step
                            if (box_x, box_y) == T:
                                return steps + 1
                            tmp.append(self.next_step)
            q = tmp
            steps += 1
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        
        br,bc = -1,-1
        sr,sc = -1,-1
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 'B':
                    br, bc = r,c
                elif grid[r][c] == 'S':
                    sr, sc = r,c
                    
                    
        
        def reachable(br,bc, sr,sc,tr,tc):
            visited = {(sr,sc)}
            def helper(curr, curc):
                if curr == tr and curc == tc:
                    return True
                for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                    newr,newc = curr+dr, curc+dc
                    if newr < 0 or newr >= rows or newc < 0 or newc >= cols: continue
                    if grid[newr][newc] == '#' or (newr,newc) == (br,bc): continue
                    if (newr,newc) in visited: continue
                    visited.add((newr,newc))
                    if helper(newr,newc): return True
                return False
            return helper(sr,sc)
                        
        
        
        seen = {(br,bc,sr,sc)}
        step = 0
        frontier = [(br,bc,sr,sc)]
        while frontier:
            newft = []
            for br,bc,sr,sc in frontier:
                if grid[br][bc] == 'T': return step
                
                for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                    newr,newc = br+dr, bc+dc
                    if newr < 0 or newr >= rows or newc < 0 or newc >= cols: continue
                    if grid[newr][newc] == '#': continue
                    targr,targc = br-dr,bc-dc
                    if targr < 0 or targr >= rows or targc < 0 or targc >= cols: continue
                    if grid[targr][targc] == '#': continue
                    if (newr,newc,targr,targc) in seen: continue
                    if not reachable(br,bc, sr,sc,targr,targc): continue
                    seen.add((newr,newc, targr,targc))
                    newft.append((newr,newc, targr,targc))
                    
            step+=1
            frontier = newft
                    
                    
        return -1
                


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return -1
        
        # Main idea: run Dijkstra's except only expand on nodes
        # that do not have a wall on the oposite side of the
        # box location. Also check for each position if we can
        # get from the old starting location to the new appropriate
        # push position
        
        self.grid = grid
        self.memo = {} # (start => dst) : True or False by DFS'ing
        dst = None
        start = None
        box_start = None
        from queue import Queue
        pq = Queue()
        for row in range(len(grid)):
            for col in range(len(grid[row])):
                elem = grid[row][col]
                if elem == \"B\":
                    box_start = (row, col)
                elif elem == \"T\":
                    dst = (row, col)
                elif elem == \"S\":
                    start = (row, col)
        
        assert dst is not None
        assert start is not None
        assert box_start is not None
        pq.put((0, box_start[0], box_start[1], start))
        
        best = set()
        while not pq.empty():
            pushes, row, col, start = pq.get()
            if (row, col, start) not in best:
                best.add((row, col, start))
                if (row, col) == dst:
                    return pushes
                if row + 1 < len(grid) and row - 1 >= 0:
                    if grid[row + 1][col] != \"#\" and grid[row - 1][col] != \"#\" and self.dfs(start[0], start[1], (row +1, col), set(), (row, col)):
                        pq.put((pushes + 1, row - 1, col, (row, col)))
                    if grid[row - 1][col] != \"#\" and grid[row + 1][col] != \"#\" and self.dfs(start[0], start[1], (row - 1, col), set(), (row, col)):
                        pq.put((pushes + 1, row + 1, col, (row, col)))
                if col + 1 < len(grid[0]) and col - 1 >= 0:
                    if grid[row][col + 1] != \"#\" and grid[row][col - 1] != \"#\" and self.dfs(start[0], start[1], (row , col + 1), set(), (row, col)):
                        pq.put((pushes + 1, row, col - 1, (row, col)))
                    if grid[row][col - 1] != \"#\" and grid[row][col + 1] != \"#\" and self.dfs(start[0], start[1], (row , col - 1), set(), (row, col)):
                        pq.put((pushes + 1, row, col + 1, (row, col)))
        return -1
    
    def dfs(self, r, c, goal, seen, box_location):
        if ((r, c), goal) in self.memo:
            return self.memo[(r, c), goal]
        if (r, c) == goal:
            return True
        if not (0 <= r < len(self.grid)):
            return False
        if not (0 <= c < len(self.grid[0])):
            return False
        if self.grid[r][c] == \"#\":
            return False
        if (r, c) == box_location:
            return False
        if (r, c) not in seen:
            seen.add((r, c))
            if self.dfs(r + 1, c, goal, seen, box_location):
                self.memo[((r, c), goal)] = True
                return True
            if self.dfs(r - 1, c, goal, seen, box_location):
                self.memo[((r, c), goal)] = True
                return True
            if self.dfs(r, c + 1, goal, seen, box_location):
                self.memo[((r, c), goal)] = True
                return True
            if self.dfs(r, c - 1, goal, seen, box_location):
                self.memo[((r, c), goal)] = True
                return True
        self.memo[((r, c), goal)] = False
        return False

import heapq
class Solution: 
    def est_distance(self, grid, target_posi, box_posi, move):
        return move + abs(target_posi[0] - box_posi[0]) + abs(target_posi[1] - box_posi[1])
    
    def isvalid_posi(self, grid, m, n, posi):
        i, j = posi
        if i<0 or i>=m or j<0 or j>=n:
            return False
        return grid[i][j] != '#'
    
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        m = len(grid)
        n = len(grid[0])
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    box_posi = (i,j)
                if grid[i][j] == 'T':
                    target_posi = (i,j)
                if grid[i][j] == 'S':
                    start_posi = (i,j)
        
        seen = set()
        seen.add((box_posi, start_posi))
        
        init_dist = self.est_distance(grid, target_posi, box_posi, 0)
        heap = [(init_dist, 0, box_posi, start_posi)]
        
        while heap:
            dist, move, current_box, current_human =  heapq.heappop(heap)
            if current_box == target_posi:
                return move
            for row_move, col_move in [(-1,0), (1,0),(0,1),(0,-1)]:
                new_human = (current_human[0] + row_move, current_human[1] + col_move)
                if not self.isvalid_posi(grid, m, n, new_human):
                    continue
                if (current_box, new_human) not in seen:
                    if new_human == current_box:
                        new_box = (current_box[0] + row_move, current_box[1] + col_move)
                        if self.isvalid_posi(grid, m, n, new_box):
                            seen.add((new_box, new_human))
                            new_dist = self.est_distance(grid, target_posi, new_box, move+1)
                            heapq.heappush(heap, (new_dist, move + 1, new_box, new_human))
                    else:
                        seen.add((current_box, new_human))
                        new_dist = self.est_distance(grid, target_posi, current_box, move)
                        heapq.heappush(heap, (new_dist, move, current_box, new_human))
        
        
        return -1
                        
                            
                        
        
        


class Solution:
    def minPushBox(self, A: List[List[str]]) -> int:
        
        def reachable(sx, sy, tsx, tsy, bx, by, A, dirs):
            m, n = len(A), len(A[0])
            visited = [[0] * 20 for _ in range(20)]
            visited[sx][sy] = 1
            q = deque()
            q.append([sx, sy])
            while q:
                sx, sy = q.popleft()
                for dx, dy in dirs:
                    nsx, nsy = sx + dx, sy + dy
                    if 0 <= nsx < m and 0 <= nsy < n and visited[nsx][nsy] == 0 and (A[nsx][nsy] in '.T' and [nsx, nsy] != [bx, by]):
                        if [nsx, nsy] == [tsx, tsy]: return True
                        visited[nsx][nsy] = 1
                        q.append([nsx, nsy])
            return False
        
        m, n = len(A), len(A[0])
        
        for i in range(m):
            for j in range(n):
                if A[i][j] == 'B':
                    bx, by = i, j
                    A[i][j] = '.'
                if A[i][j] == 'S':
                    sx, sy = i, j
                    A[i][j] = '.'
        dirs = [[-1,0],[1,0],[0,-1],[0,1]]
        visited = [[0] * 400 for _ in range(400)]
        visited[bx*20+by][sx*20+sy] = 1
        
        q = deque()
        q.append([bx, by, sx, sy, 0])
        
        while q:
            # print(q)
            bx, by, sx, sy, step = q.popleft()
            for dx, dy in dirs:
                nbx, nby = bx + dx, by + dy
                if 0 <= nbx < m and 0 <= nby < n and A[nbx][nby] in '.T':
                    nsx, nsy = 2 * bx - nbx, 2 * by - nby
                    if 0 <= nsx < m and 0 <= nsy < n and reachable(sx, sy, nsx, nsy, bx, by, A, dirs) and visited[nbx*20+nby][nsx*20+nsy] == 0:
                        if A[nbx][nby] == 'T': return step + 1
                        visited[nbx*20+nby][nsx*20+nsy] = 1
                        q.append([nbx,nby,nsx,nsy,step+1])
        return -1


class Solution:
    # DFS failed
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        cache = {}
        visited = set()
        def dp(b, p):
            if not (0<=b[0]<m and 0<=b[1]<n and 0<=p[0]<m and 0<=p[1]<n) or grid[b[0]][b[1]] == '#' or grid[p[0]][p[1]] == '#' or b == p:
                return float(\"inf\")
            if grid[b[0]][b[1]] == 'T':
                return 0
            if (b, p) in cache:
                return cache[(b, p)]
            if (b, p) in visited:
                return float(\"inf\")
            visited.add((b, p))
            ans = float(\"inf\")
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)
            ans = min(ans, min(dp(b, pp) for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1))))
            visited.remove((b, p))
            cache[(b, p)] = ans
            return ans
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
        ans = dp(b, p)
        print(cache)
        return -1 if ans == float(\"inf\") else ans
    
    # BFS
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        q = collections.deque()
        visited = set()
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
                    
        q.append((b, p, 0))
        visited.add((b, p))
        while q:
            b, p, c = q.popleft()
            if grid[b[0]][b[1]] == 'T':
                return c
            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):
                if (b, pp) not in visited and 0<=pp[0]<m and 0<=pp[1]<n and grid[pp[0]][pp[1]] != '#' and b != pp:
                    q.appendleft((b, pp, c))
                    visited.add((b, pp))
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                p = b
                b = (b[0]+delta[0], b[1]+delta[1])
                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':
                    q.append((b, p, c+1))
                    visited.add((b, p))
        return -1
    
    # BFS + A*
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        from heapq import heappop, heappush
        
        q = []
        visited = set()
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    p = (i, j)
                if grid[i][j] == 'T':
                    t = (i, j)
                
                    
        q.append((abs(t[0]-b[0]) + abs(t[1]-b[1]), 0, b, p))
        visited.add((b, p))
        while q:
            gh, g, b, p = heappop(q)
            if b == t:
                return g
            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):
                if (b, pp) not in visited and 0<=pp[0]<m and 0<=pp[1]<n and grid[pp[0]][pp[1]] != '#' and b != pp:
                    heappush(q, (gh, g, b, pp))
                    visited.add((b, pp))
            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:
                delta = (b[0] - p[0], b[1] - p[1])
                p = b
                b = (b[0]+delta[0], b[1]+delta[1])
                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':
                    heappush(q, (g+1+abs(t[0]-b[0]) + abs(t[1]-b[1]), g+1, b, p))
                    visited.add((b, p))
        return -1
            
            

from heapq import heappush, heappop
class Solution:
    def minPushBox(self, A: List[List[str]]) -> int:
        m, n = len(A), len(A[0])
        for i in range(m):
            for j in range(n):
                if A[i][j] == 'B':
                    b_pos = (i, j)
                elif A[i][j] == 'T':
                    t_pos = (i, j)
                elif A[i][j] == 'S':
                    p_pos = (i, j)
        
        def estimate(pos):
            return abs(t_pos[0] - pos[0]) + abs(t_pos[1] - pos[1])
        seen = {(p_pos, b_pos)}
        heap = [[estimate(b_pos), 0, p_pos, b_pos]]
        nbs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while heap:
            est, cost, person, box = heappop(heap)
            if box == t_pos:
                return cost
            for a, b in nbs:
                x, y = person[0] + a, person[1] + b
                if 0 <= x < m and 0 <= y < n and A[x][y] != '#':
                    n_person = (x, y)
                    n_box = box
                    n_cost = cost
                    if n_person == box:
                        n_box = (x + a, y + b)
                        n_cost += 1
                    if 0 <= n_box[0] < m and 0 <= n_box[1] < n and A[n_box[0]][n_box[1]] != '#' and (n_person, n_box) not in seen:
                        heappush(heap, [estimate(n_box) + n_cost, n_cost, n_person, n_box])
                        seen.add((n_person, n_box))
        return -1


from collections import deque 
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        def check(sx, sy, px, py):
            q = deque([(px, py)])
            visited = set((px, py))
            while q:
                x, y = q.popleft()
                if (x, y) == (sx, sy):
                    return True
                for dx, dy in (-1, 0), (0,-1), (0,1), (1,0):
                    x_, y_ = x+dx, y+dy
                    if valid(x_, y_) and (x_,y_) not in visited:
                        visited.add((x_, y_))
                        q.append((x_, y_))
            return False
        
        def valid(x_, y_):
            return 0<=x_<m and 0<=y_<n and grid[x_][y_] ==\".\"
        
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"B\":
                    bx, by = i, j
                    grid[i][j] = \".\"
                if grid[i][j] == \"S\":
                    sx, sy = i, j
                    grid[i][j] = \".\"
                if grid[i][j] == \"T\":
                    tx, ty = i, j
                    
        q = deque([(bx, by, x, y) for x, y in [(-1, 0), (0,-1), (0,1), (1,0)] if (valid(bx+x, by+y) and check(bx+x, by+y,sx,sy))])
        visited = set()
        level = 0
        while q:
            level += 1
            print(q)
            for _ in range(len(q)):
                
                bx, by, x, y = q.popleft()

                visited.add((bx, by, x, y))
                x_, y_ = bx-x, by-y
                if (x_, y_) == (tx, ty):
                    return level
                if valid(x_,y_) and (x_, y_, x, y) not in visited:
                    q.append((x_, y_, x, y))
                    visited.add((x_, y_, x, y))
                    grid[x_][y_] = \"b\"
                    # print((x_, y_, x, y))
                    px, py = x_+x, y_+y
                    for dx, dy in (-1, 0), (0,-1), (0,1), (1,0):
                        x2, y2 = x_+dx, y_+dy
                        # print(x2, y2)
                        
                        if (x2, y2) != (px, py) and valid(x2, y2) and check(x2, y2, px, py) and (x_,y_,x2-x_,y2-y_) not in visited:
                            q.append((x_,y_,x2-x_,y2-y_))
                            visited.add((x_,y_,x2-x_,y2-y_))
                            # print((x_,y_,x_-x2,y_-y2))
                    grid[x_][y_] = \".\"
        return -1
            
            
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'T':
                    t = (i, j)
                elif grid[i][j] == 'S':
                    s = (i, j)
                elif grid[i][j] == 'B':
                    b = (i, j)
        
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = [tuple(s + b)]
        seen = set(q)
        steps = 0
        while q:
            nq = []
            for si, sj, bi, bj in q:
                if t == (bi, bj): 
                    return steps
                for di, dj in dirs:
                    nsi, nsj = si + di, sj + dj
                    if nsi == bi and nsj == bj:
                        nbi, nbj = bi + di, bj + dj
                        ds = 1
                    else:
                        nbi, nbj = bi, bj
                        ds = 0
                    if not (0 <= nsi < n and 0 <= nsj < m): 
                        continue
                    if not (0 <= nbi < n and 0 <= nbj < m): 
                        continue
                    if grid[nsi][nsj] == '#' or grid[nbi][nbj] == '#': 
                        continue
                    nsb = (nsi, nsj, nbi, nbj)
                    if nsb in seen: 
                        continue
                    seen.add(nsb)
                    if ds == 0:
                        q.append(nsb)
                    else:
                        nq.append(nsb)
            q = nq
            steps += 1
        return -1


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'
        dist = lambda i, j: abs(i - ti) + abs(j - tj)
        
        m, n = len(grid), len(grid[0])
        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        pi, pj, bi, bj = 0, 0, 0, 0
        ti, tj = 0, 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    pi, pj = i, j
                if grid[i][j] == 'B':
                    bi, bj = i, j
                if grid[i][j] == 'T':
                    ti, tj = i, j
        for i, j in [[ti, tj], [bi, bj]]:
            k = 0
            for di, dj in dij:
                ii, jj = i + di, j + dj
                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':
                    k += 1
            if k == 4:
                return -1
        q = [(0, pi, pj, bi, bj)]
        visited = {(pi, pj, bi, bj)}
        pushes = 1e6
        while q:
            psh, pi, pj, bi, bj = heapq.heappop(q)
            if grid[bi][bj] == 'T':
                return psh
            for di, dj in dij:
                pii, pjj = pi + di, pj + dj
                if not check(pii, pjj):
                    continue
                if pii == bi and pjj == bj:
                    bii, bjj = bi + di, bj + dj
                    if not check(bii, bjj):
                        continue
                    if grid[bii][bjj] == 'T':
                        return psh + 1
                    st = (pii, pjj, bii, bjj)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh + 1, pii, pjj, bii, bjj))
                else:
                    st = (pii, pjj, bi, bj)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh, pii, pjj, bi, bj))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 'T':
                    target = (r,c)
                if grid[r][c] == 'S':
                    start_person = (r,c)
                if grid[r][c] == 'B':
                    start_box = (r,c)
            
        def heuristic(box):
            return abs(target[0]-box[0]) + abs(target[1]-box[1])

        def out_bounds(location):
            r,c=location
            return r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == '#'

        heap = [[heuristic(start_box), 0, start_person, start_box]]
        vis = set([start_person,start_box])
        while heap:
            _, moves, person, box = heapq.heappop(heap)
            if box == target:
                return moves

            for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_person = (person[0]+dr,person[1]+dc)
                if out_bounds(new_person):
                    continue

                if new_person == box:
                    new_box = (box[0]+dr, box[1]+dc)
                    if out_bounds(new_box) or (new_person, new_box) in vis:
                        continue
                    heapq.heappush(heap, [heuristic(new_box)+moves+1, moves+1, new_person, new_box])
                    vis.add((new_person, new_box))
                else:
                    if (new_person, box) in vis:
                        continue
                    heapq.heappush(heap, [heuristic(box)+moves, moves, new_person, box])
                    vis.add((new_person, box))

        return -1
                        
                    
                    
                    
                    


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'
        dist = lambda i, j: abs(i - ti) + abs(j - tj)
        
        m, n = len(grid), len(grid[0])
        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        pi, pj, bi, bj = 0, 0, 0, 0
        ti, tj = 0, 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    pi, pj = i, j
                if grid[i][j] == 'B':
                    bi, bj = i, j
                if grid[i][j] == 'T':
                    ti, tj = i, j
        for i, j in [[ti, tj], [bi, bj]]:
            k = 0
            for di, dj in dij:
                ii, jj = i + di, j + dj
                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':
                    k += 1
            if k == 4:
                return -1
        q = [(0, pi * n + pj, bi * n + bj)]
        visited = {(pi * n + pj, bi * n + bj)}
        pushes = 1e6
        while q:
            psh, p, b = heapq.heappop(q)
            pi, pj = divmod(p, n)
            bi, bj = divmod(b, n)
            if grid[bi][bj] == 'T':
                return psh
            for di, dj in dij:
                pii, pjj = pi + di, pj + dj
                if not check(pii, pjj):
                    continue
                if pii == bi and pjj == bj:
                    bii, bjj = bi + di, bj + dj
                    if not check(bii, bjj):
                        continue
                    if grid[bii][bjj] == 'T':
                        return psh + 1
                    st = (pii * n + pjj, bii * n + bjj)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh + 1, pii * n + pjj, bii * n + bjj))
                else:
                    st = (pii * n + pjj, b)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh, pii * n + pjj, b))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')
        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')
        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')
        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')
        heap = [(0, si, sj, boxi, boxj)]
        def add(moves, *state, added=set()):
            if state not in added:
                heapq.heappush(heap, (moves, *state))
                added.add(state)
        while heap:
            moves, si, sj, boxi, boxj = heapq.heappop(heap)
            if (boxi, boxj) == target:
                return moves
            for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
                ni, nj = si + dx, dy + sj
                if (ni, nj) == (boxi, boxj):
                    if (boxi + dx, boxj + dy) in free:
                        add(moves + 1, ni, nj, boxi + dx, boxj + dy)
                elif (ni, nj) in free:
                    add(moves, ni, nj, boxi, boxj)
        return -1


import heapq

class Solution:
  def minPushBox(self, grid: List[List[str]]) -> int:
    # bfs, dfs, a-star search
    # key:
    # represent the state using (xb, yb, xp, yp), box and storekeeper coordinates, where storekeeper can move around,
    # up down left and right, and push the box when storekeeper move to box position and the cell next to it is empty.
    m, n = len(grid), len(grid[0])
    xb, yb, xs, ys, xt, yt = -1, -1, -1, -1, -1, -1
    for x in range(m):
      for y in range(n):
        if grid[x][y] == 'B':
          xb, yb = x, y
          grid[x][y] = '.'
        if grid[x][y] == 'S':
          xs, ys = x, y
          grid[x][y] = '.'
        if grid[x][y] == 'T':
          xt, yt = x, y
          grid[x][y] = '.'
    # a-star search
    # heuristic: h(box, target) = abs(xb - xt) + abs(yb - yt), as the lower bound of moves to push box to target.
    
    # init
    q, seen = [(abs(xb - xt) + abs(yb - yt) + 0, 0, xb, yb, xs, ys)], set()
    while q:
      h, d, xb, yb, xs, ys = heapq.heappop(q)
      if (xb, yb) == (xt, yt):
        return d
      if (xb, yb, xs, ys) not in seen:
        seen.add((xb, yb, xs, ys))
        # storekeeper moves around and pushes the box when step into box coordinates
        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
          xr, yr = xs + dx, ys + dy
          if 0 <= xr < m and 0 <= yr < n and grid[xr][yr] == '.':
            if (xr, yr) == (xb, yb):
              xc, yc = xb + dx, yb + dy
              if 0 <= xc < m and 0 <= yc < n and grid[xc][yc] == '.':
                heapq.heappush(q, (abs(xc - xt) + abs(yc - yt) + d + 1, d + 1, xc, yc, xr, yr))
            else:
              heapq.heappush(q, (h, d, xb, yb, xr, yr))
    return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')
        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')
        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')
        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')
        visited = set()
        heap = [(0, si, sj, boxi, boxj)]
        while heap:
            moves, si, sj, boxi, boxj = heapq.heappop(heap)
            if (boxi, boxj) == target:
                return moves
            if (si, sj, boxi, boxj) in visited:
                continue
            visited.add((si, sj, boxi, boxj))
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni, nj = si + dx, dy + sj
                if (ni, nj) == (boxi, boxj) and (boxi + dx, boxj + dy) in free and (ni, nj, boxi + dx, boxj + dy) not in visited:
                    heapq.heappush(heap, (moves + 1, ni, nj, boxi + dx, boxj + dy))
                elif (ni, nj) in free and (ni, nj) != (boxi, boxj) and (ni, nj, boxi, boxj) not in visited:
                    heapq.heappush(heap, (moves, ni, nj, boxi, boxj))
        return -1         

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        M, N = len(grid), len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j] in ['#', '.']:
                    continue
                if grid[i][j] == 'S':
                    player = (i, j)
                elif grid[i][j] == 'B':
                    box = (i, j)
                else:
                    target = (i, j)
        
        @lru_cache(None)
        def reach(player, pos, box):
            i, j = pos
            if not (0 <= i < M and 0 <= j < N and grid[i][j] != '#'):
                return False
            hp = [player]
            seen = set([player])
            while hp:
                player = heapq.heappop(hp)
                if player == pos:
                    return True
                p0, p1 = player
                for i, j in [(p0 - 1, p1), (p0 + 1, p1), (p0, p1 - 1), (p0, p1 + 1)]:
                    if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and (i, j) != box and (i, j) not in seen:
                        seen.add((i, j))
                        heapq.heappush(hp, (i, j))
            return False
        
        seen = set([(box, player)])
        hp = [(0, box, player)]
        while hp:
            step, box, player = heapq.heappop(hp)
            # print(box)
            if box == target:
                return step
            b0, b1 = box
            for i, j in [(b0 - 1, b1), (b0 + 1, b1), (b0, b1 - 1), (b0, b1 + 1)]:
                if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and ((i, j), player) not in seen and reach(player, (
                b0 * 2 - i, b1 * 2 - j), box):
                    seen.add(((i, j), player))
                    heapq.heappush(hp, (step + 1, (i, j), box))
        return -1
                    
                
                
                
                
                
                
                
                
                


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        qq = collections.deque()
        xx = [1,2,3]
        yy = [4,5,6]
        qq.appendleft([7,8,9])
        qq.appendleft(yy)
        print(len(qq))
        
        px,py,bx,by,tx,ty = 0,0,0,0,0,0
        visited = {}
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"B\":
                    bx = i
                    by = j
                    grid[i][j] = \".\"
                elif grid[i][j] == \"T\":
                    tx = i
                    ty = j
                    grid[i][j] = \".\"
                elif grid[i][j] == \"S\":
                    px = i
                    py = j
                    
                    grid[i][j] = \".\"
                
        
        dir0 = [[0,1],[0,-1],[1,0],[-1,0]]
        visited[(bx,by,px,py)] = 0
        #q = [[bx,by,px,py]]
        q = collections.deque()
        q.append([bx,by,px,py])
        step = 0
        while q:
            #co  = q.pop(0)
            co  = q.popleft()
            if co[0]==tx and co[1]==ty:
                return visited[(co[0],co[1],co[2],co[3])]
            
            for y in range(len(dir0)):
                newx = co[2] + dir0[y][0]
                newy = co[3] + dir0[y][1]
                if newx<0 or newx>= m or newy<0 or newy>=n or (co[0],co[1],newx,newy) in visited:
                    continue
                if newx==co[0] and newy==co[1]:
                    continue
                if grid[newx][newy]!=\".\":
                    continue
                #q.insert(0,[co[0],co[1],newx,newy])
                q.appendleft([co[0],co[1],newx,newy])
                step = visited.get((co[0],co[1],co[2],co[3]),0)
                visited[(co[0],co[1],newx,newy)] = step
                
            
            if abs(co[0]-co[2]) + abs(co[1]-co[3]) == 1:
                for y in range(len(dir0)):
                    if co[2]+dir0[y][0]==co[0] and co[3] + dir0[y][1] == co[1]:
                        newx = co[0] + dir0[y][0]
                        newy = co[1] + dir0[y][1]
                        if newx<0 or newx>= m or newy<0 or newy>=n or (newx,newy,co[0],co[1]) in visited:
                            continue
                        if grid[newx][newy]!=\".\":
                            continue                
                        q.append([newx,newy,co[0],co[1]])
                        step = visited.get((co[0],co[1],co[2],co[3]),0)
                        visited[(newx,newy,co[0],co[1])] = step+1
        return -1       
            
            
            
            
            
            

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        free = set()
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'T':
                    tx, ty = i, j
                    free.add((i, j))
                if grid[i][j] == 'S':
                    sx, sy = i, j
                    free.add((i, j))
                if grid[i][j] == 'B':
                    bx, by = i, j
                    free.add((i, j))
                if grid[i][j] == '.':
                    free.add((i, j))
        pq = [(0, sx, sy, bx, by)]
        visited = set()
        direction = [(0,1), (1,0), (-1,0), (0,-1)]
        while pq:
            moves, sx, sy, bx, by = heapq.heappop(pq)
            if bx == tx and by == ty:
                return moves
            if (sx, sy, bx, by) in visited:
                continue
            visited.add((sx, sy, bx, by))
            for d in direction:
                dx, dy = d
                if sx + dx == bx and sy + dy == by and (bx + dx, by + dy) in free:
                    heapq.heappush(pq, (moves + 1, sx + dx, sy + dy, bx + dx, by + dy))
                if (sx + dx, sy + dy) in free and (sx + dx, sy + dy) != (bx, by) and (sx + dx, sy + dy, bx, by) not in visited:
                    heapq.heappush(pq, (moves, sx + dx, sy + dy, bx, by))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        r, c = len(grid), len(grid[0])
        dire = [[0, 1], [0, -1], [-1, 0], [1, 0]]
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 'T':
                    T = (i, j)
                elif grid[i][j] == 'B':
                    B = (i, j)
                elif grid[i][j] == 'S':
                    S = (i, j)

        def check1(x, y):
            return x >= 0 and x < r and y >= 0 and y < c and grid[x][y] != '#'

        def canMoveTo(e, b, q, vis):
            while q:
                pre = q.pop(0)
                if pre == e:
                    return True

                for i, j in dire:
                    nx, ny = pre[0] + i, pre[1] + j
                    if check1(nx, ny) and \\
                        (nx, ny) != b and (nx, ny) not in vis:
                        q.append((nx, ny))
                        vis.add((nx, ny))
            return False

        def move(e, q, vis):
            res = 0
            while q:
                for _ in range(len(q)):
                    b, p = q.pop(0)
                    if b == e:
                        return res
                    
                    for i, j in dire:
                        nx, ny = b[0] + i, b[1] + j
                        if check1(nx, ny) and \\
                            check1(b[0] - i, b[1] - j) and\\
                            ((nx, ny), b) not in vis and \\
                            canMoveTo((b[0] - i, b[1] - j), b, [p], set([p])):
                            q.append(((nx, ny), b))
                            vis.add(((nx, ny), b))
                res += 1
            return -1

        return move(T, [(B, S)], set([(B, S)]))

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    bi, bj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    si, sj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    ti, tj = i, j
                    grid[i][j] = '.'
        q = [(bi, bj, si, sj, 0)]
        seen = {(bi, bj, si, sj)}
        while q:
            bi, bj, si, sj, dist = q.pop(0)
            if (bi, bj) == (ti, tj):
                return dist
            validMoves = self.canMoveTo(grid, bi, bj, si, sj, {(si, sj)})
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                si_new, sj_new = bi+dx, bj+dy
                bi_new, bj_new = bi-dx, bj-dy
                if (bi_new, bj_new, bi, bj) not in seen and (si_new, sj_new) in validMoves and 0 <= bi_new < m and 0 <= bj_new < n and grid[bi_new][bj_new] == '.':
                    q.append((bi_new, bj_new, bi, bj, dist+1))
                    seen.add((bi_new, bj_new, bi, bj))
        return -1
    
    def canMoveTo(self, grid, bi, bj, si, sj, validSet):
        m, n = len(grid), len(grid[0])
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) in validSet:
                continue
            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                validSet.add((i, j))
                self.canMoveTo(grid, bi, bj, i, j, validSet)
        return validSet
    
    '''
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            if si == si_new and sj == sj_new:
                return True
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return False

    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):
        m, n = len(grid), len(grid[0])
        if si == si_new and sj == sj_new:
            return True
        visited.add((si, sj))
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#' and self.canMoveTo(grid, bi, bj, i, j, si_new, sj_new, visited):
                return True
        return False
    '''    

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        self.empty = [['.' for _ in range(n)] for _ in range(m)]
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == 'B': start = (i,j)
                if c == 'S': player = (i,j)
                if c == 'T': target = (i,j)
                if c == '#': self.empty[i][j] = '#'
        visit = [[0 for _ in range(n)] for _ in range(m)]
        visit[start[0]][start[1]] += 1
        deq = collections.deque([(start,player,(-1,-1))])
        push = 0
        while deq and push < m * n:
            sz = len(deq)
            for i in range(sz):
                box,player, previous = deq.popleft()
                if box == target: return push
                cango = self.player(player, box,self.empty)
                for d in self.direction:
                    nr, nc = box[0] + d[0], box[1] + d[1]
                    pr,pc = box[0] + d[2], box[1] + d[3]
                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:
                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:
                            visit[nr][nc] +=1
                            deq.append(((nr,nc),(pr,pc),box))
            push += 1
        return -1
    
    def player(self, player, box, grid):
        m, n = len(grid), len(grid[0])
        visit = [[False for _ in range(n)] for _ in range(m)]
        visit[player[0]][player[1]] = True
        deq = collections.deque([player])
        while deq:
            sz = len(deq)
            for i in range(sz):
                cur = deq.popleft()
                for d in self.direction:
                    nr, nc = cur[0] + d[0], cur[1] + d[1]
                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):
                        visit[nr][nc] = True
                        deq.append((nr,nc))
        return visit
    
    def __init__(self):
        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))
        self.empty = None

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')
        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')
        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')
        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')
        visited = set()
        heap = [(0, si, sj, boxi, boxj)]
        while heap:
            moves, si, sj, boxi, boxj = heapq.heappop(heap)
            if (boxi, boxj) == target:
                return moves
            if (si, sj, boxi, boxj) in visited:
                continue
            visited.add((si, sj, boxi, boxj))
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni, nj = si + dx, dy + sj
                if (ni, nj) == (boxi, boxj) and (boxi + dx, boxj + dy) in free and (ni, nj, boxi + dx, boxj + dy) not in visited:
                    heapq.heappush(heap, (moves + 1, ni, nj, boxi + dx, boxj + dy))
                elif (ni, nj) in free and (ni, nj) != (boxi, boxj) and (ni, nj, boxi, boxj) not in visited:
                    heapq.heappush(heap, (moves, ni, nj, boxi, boxj))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    bi, bj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    si, sj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    ti, tj = i, j
                    grid[i][j] = '.'
        q = [(bi, bj, si, sj, 0)]
        seen = {(bi, bj, si, sj)}
        while q:
            bi, bj, si, sj, dist = q.pop(0)
            if (bi, bj) == (ti, tj):
                return dist
            validSet = self.canMoveTo(grid, bi, bj, si, sj)
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                si_new, sj_new = bi+dx, bj+dy
                bi_new, bj_new = bi-dx, bj-dy
                if (bi_new, bj_new, bi, bj) not in seen and (si_new, sj_new) in validSet and 0 <= bi_new < m and 0 <= bj_new < n and grid[bi_new][bj_new] == '.':
                    q.append((bi_new, bj_new, bi, bj, dist+1))
                    seen.add((bi_new, bj_new, bi, bj))
        return -1
    
    def canMoveTo(self, grid, bi, bj, si, sj):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return visited
    
    '''
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            if si == si_new and sj == sj_new:
                return True
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return False
        
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):
        m, n = len(grid), len(grid[0])
        if si == si_new and sj == sj_new:
            return True
        visited.add((si, sj))
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#' and self.canMoveTo(grid, bi, bj, i, j, si_new, sj_new, visited):
                return True
        return False
        
    def canMoveTo(self, grid, bi, bj, si, sj, validSet):
        m, n = len(grid), len(grid[0])
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) in validSet:
                continue
            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                validSet.add((i, j))
                self.canMoveTo(grid, bi, bj, i, j, validSet)
        return validSet
    '''    

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B':
                    bi, bj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    si, sj = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    ti, tj = i, j
                    grid[i][j] = '.'
        q = [(bi, bj, si, sj, 0)]
        seen = {(bi, bj, si, sj)}
        while q:
            bi, bj, si, sj, dist = q.pop(0)
            if (bi, bj) == (ti, tj):
                return dist
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                si_new, sj_new = bi+dx, bj+dy
                bi_new, bj_new = bi-dx, bj-dy
                if (bi_new, bj_new, bi, bj) not in seen and self.canMoveTo(grid, bi, bj, si, sj, si_new, sj_new, set()) and 0 <= bi_new < m and 0 <= bj_new < n and grid[bi_new][bj_new] == '.':
                    q.append((bi_new, bj_new, bi, bj, dist+1))
                    seen.add((bi_new, bj_new, bi, bj))
        return -1
    
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):
        m, n = len(grid), len(grid[0])
        if si == si_new and sj == sj_new:
            return True
        visited.add((si, sj))
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#' and self.canMoveTo(grid, bi, bj, i, j, si_new, sj_new, visited):
                return True
        return False
    '''
    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
        m, n = len(grid), len(grid[0])
        q = [(si, sj)]
        visited = {(si, sj)}
        while q:
            si, sj = q.pop(0)
            if si == si_new and sj == sj_new:
                return True
            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
                i, j = si+dx, sj+dy
                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                    q.append((i, j))
                    visited.add((i, j))
        return False


        
    def canMoveTo(self, grid, bi, bj, si, sj, validSet):
        m, n = len(grid), len(grid[0])
        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
            i, j = si+dx, sj+dy
            if (i, j) in validSet:
                continue
            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':
                validSet.add((i, j))
                self.canMoveTo(grid, bi, bj, i, j, validSet)
        return validSet
    '''    

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'
        
        m, n = len(grid), len(grid[0])
        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        pi, pj, bi, bj = 0, 0, 0, 0
        ti, tj = 0, 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    pi, pj = i, j
                if grid[i][j] == 'B':
                    bi, bj = i, j
                if grid[i][j] == 'T':
                    ti, tj = i, j
        for i, j in [[ti, tj], [bi, bj]]:
            k = 0
            for di, dj in dij:
                ii, jj = i + di, j + dj
                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':
                    k += 1
            if k == 4:
                return -1
        q = [(0, pi, pj, bi, bj)]
        visited = {(pi, pj, bi, bj)}
        pushes = 1e6
        while q:
            psh, pi, pj, bi, bj = heapq.heappop(q)
            if grid[bi][bj] == 'T':
                pushes = min(pushes, psh)
                continue
            for di, dj in dij:
                pii, pjj = pi + di, pj + dj
                if not check(pii, pjj):
                    continue
                if pii == bi and pjj == bj:
                    bii, bjj = bi + di, bj + dj
                    if not check(bii, bjj):
                        continue
                    st = (pii, pjj, bii, bjj)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh + 1, pii, pjj, bii, bjj))
                else:
                    st = (pii, pjj, bi, bj)
                    if st not in visited:
                        visited.add(st)
                        heapq.heappush(q, (psh, pii, pjj, bi, bj))
        return pushes if pushes < 1e6 else -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        self.empty = [['.' for _ in range(n)] for _ in range(m)]
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == 'B': start = (i,j)
                if c == 'S': player = (i,j)
                if c == 'T': target = (i,j)
                if c == '#': self.empty[i][j] = '#'
        visit = [[0 for _ in range(n)] for _ in range(m)]
        visit[start[0]][start[1]] += 1
        deq = collections.deque([(start,player,(-1,-1))])
        push = 0
        while deq and push < m * n:
            sz = len(deq)
            for i in range(sz):
                box,player, previous = deq.popleft()
                if box == target: return push
                cango = self.player(player, box,self.empty)
                for d in self.direction:
                    nr, nc = box[0] + d[0], box[1] + d[1]
                    pr,pc = box[0] + d[2], box[1] + d[3]
                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:
                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:
                            visit[nr][nc] +=1
                            deq.append(((nr,nc),(pr,pc),box))
            push += 1
        return -1
    
    def player(self, player, box, grid):
        m, n = len(grid), len(grid[0])
        visit = [[False for _ in range(n)] for _ in range(m)]
        togo = [[False for _ in range(n)] for _ in range(m)]
        visit[player[0]][player[1]], togo[player[0]][player[1]] = True, True
        deq = collections.deque([player])
        while deq:
            sz = len(deq)
            for i in range(sz):
                cur = deq.popleft()
                for d in self.direction:
                    nr, nc = cur[0] + d[0], cur[1] + d[1]
                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):
                        visit[nr][nc] = True
                        togo[nr][nc] = True
                        deq.append((nr,nc))
        return visit
    
    def __init__(self):
        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))
        self.empty = None

class Solution:
    FLOOR = \".\"
    WALL = \"#\"
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        player, box, target = (0, 0), (0, 0), (0, 0)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"S\": player = (i, j)
                if grid[i][j] == \"B\": box = (i, j)
                if grid[i][j] == \"T\": target = (i, j)
        
        hq = [(abs(target[0] - box[0]) + abs(target[1] - box[1]), 0, box, player)]
        steps = collections.defaultdict(int)
        
        while len(hq) > 0:
            curr_heuristic_est, curr_steps, (curr_i, curr_j), player = heappop(hq)
            if (curr_i, curr_j) == target:
                return curr_steps
            
            for next_i, next_j in self._get_next(grid, curr_i, curr_j, player):
                if (((next_i, next_j), (curr_i, curr_j))) not in steps or curr_steps + 1 < steps[((next_i, next_j), (curr_i, curr_j))]:
                    player = (curr_i, curr_j)
                    steps[((next_i, next_j), (curr_i, curr_j))] = curr_steps + 1
                    heappush(hq, (curr_steps + 1 + abs(target[0]-next_i) + abs(target[1]-next_j), curr_steps + 1, (next_i, next_j), player))
                    
        return -1
                   
        
    def _get_next(self, grid, curr_i, curr_j, player):
        \"\"\"
        Return a list of posible positions the box could be moved to. There are basically 4 choices
        \"\"\"
        m, n = len(grid), len(grid[0])
        res = []
        if curr_i - 1 >= 0 and grid[curr_i - 1][curr_j] != self.WALL and self._can_player_reach(grid, player, (curr_i + 1, curr_j), (curr_i, curr_j), set()):
            res.append((curr_i - 1, curr_j))
        if curr_i + 1 < m and grid[curr_i + 1][curr_j] != self.WALL and self._can_player_reach(grid, player, (curr_i - 1, curr_j), (curr_i, curr_j), set()):
            res.append((curr_i + 1, curr_j))
        if curr_j - 1 >= 0 and grid[curr_i][curr_j - 1] != self.WALL and self._can_player_reach(grid, player, (curr_i, curr_j + 1), (curr_i, curr_j), set()):
            res.append((curr_i, curr_j - 1))
        if curr_j + 1 < n and grid[curr_i][curr_j + 1] != self.WALL and self._can_player_reach(grid, player, (curr_i, curr_j - 1), (curr_i, curr_j), set()):
            res.append((curr_i, curr_j + 1))
        return res
    
    
    def _can_player_reach(self, grid, curr_pos, dst, box, visited):
        \"\"\"
        Return if player can reach dst position by doing bfs/dfs
        \"\"\"
        m, n = len(grid), len(grid[0])
        if curr_pos[0] < 0 or curr_pos[0] >= m or curr_pos[1] < 0 or curr_pos[1] >= n:
            return False
        if curr_pos == dst:
            return True
        
        for delta_i, delta_j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
            next_i, next_j = curr_pos[0] + delta_i, curr_pos[1] + delta_j
            if 0 <= next_i < m and 0 <= next_j < n:
                if grid[next_i][next_j] != self.WALL:
                    if (next_i, next_j) not in visited and (next_i, next_j) != box:
                        visited.add((next_i, next_j))
                        if self._can_player_reach(grid, (next_i, next_j), dst, box, visited):
                            return True
        return False

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m,n=len(grid),len(grid[0])
        dirs=[(0,1),(0,-1),(1,0),(-1,0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='S':
                    S=(i,j)
                if grid[i][j]=='B':
                    B=(i,j)
                if grid[i][j]=='T':
                    T=(i,j)
                    
                    
        def check(x,y):    #判断这个位置是否有效
            return 0<=x<m and 0<=y<n and grid[x][y]!='#'
                    
            
        def canmoveto(e,b,q,visit):          #判断人能否到达目标位置
            while q:
                p=q.pop(0)
                if p==e:
                    return True
                for dx,dy in dirs:
                    nx,ny=p[0]+dx,p[1]+dy
                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:
                        q.append((nx,ny))
                        visit.add((nx,ny))
            return False
        
        def move(e,q,visit):   #判断人能否把箱子推到目标位置
            res = 0
            while q:
                size=len(q)
                for _ in range(size):
                    b, p = q.pop(0)
                    if b == e:
                        return res
                    
                    for dx,dy in dirs:
                        nbx, nby = b[0] +dx, b[1] +dy
                        npx,npy=b[0]-dx,b[1]-dy
                        if check(nbx, nby) and \\
                            check(npx,npy) and\\
                            ((nbx, nby), b) not in visit and \\
                            canmoveto((npx,npy), b, [p], set([p])):
                            q.append(((nbx, nby), b))
                            visit.add(((nbx, nby), b))
                res += 1
            return -1
        return move(T,[(B,S)],set([(B,S)]))
                        
                
                
        
        

class Solution:
    FLOOR = \".\"
    WALL = \"#\"
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        player, box, target = (0, 0), (0, 0), (0, 0)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == \"S\": player = (i, j)
                if grid[i][j] == \"B\": box = (i, j)
                if grid[i][j] == \"T\": target = (i, j)
        print(box, target)
        
        hq = [(abs(target[0] - box[0]) + abs(target[1] - box[1]), 0, box, player)]
        steps = collections.defaultdict(int)
        # steps[box] = 0
        
        while len(hq) > 0:
            curr_heuristic_est, curr_steps, (curr_i, curr_j), player = heappop(hq)
            print(curr_heuristic_est, curr_steps, (curr_i, curr_j), player)
            if (curr_i, curr_j) == target:
                return curr_steps
            
            for next_i, next_j in self._get_next(grid, curr_i, curr_j, player):
                if (((next_i, next_j), (curr_i, curr_j))) not in steps or curr_steps + 1 < steps[((next_i, next_j), (curr_i, curr_j))]:
                    player = (curr_i, curr_j)
                    steps[((next_i, next_j), (curr_i, curr_j))] = curr_steps + 1
                    heappush(hq, (curr_steps + 1 + abs(target[0]-next_i) + abs(target[1]-next_j), curr_steps + 1, (next_i, next_j), player))
                    
        return -1
                   
        
    def _get_next(self, grid, curr_i, curr_j, player):
        \"\"\"
        Return a list of posible positions the box could be moved to. There are basically 4 choices
        \"\"\"
        m, n = len(grid), len(grid[0])
        res = []
        if (curr_i, curr_j) == (2, 1):
            print(curr_i, curr_j, grid[curr_i - 1][curr_j], player)
        if curr_i - 1 >= 0 and grid[curr_i - 1][curr_j] != self.WALL and self._can_player_reach(grid, player, (curr_i + 1, curr_j), (curr_i, curr_j), set()):
            res.append((curr_i - 1, curr_j))
        if (curr_i, curr_j) == (2, 1):
            print(res)
        if curr_i + 1 < m and grid[curr_i + 1][curr_j] != self.WALL and self._can_player_reach(grid, player, (curr_i - 1, curr_j), (curr_i, curr_j), set()):
            res.append((curr_i + 1, curr_j))
        if curr_j - 1 >= 0 and grid[curr_i][curr_j - 1] != self.WALL and self._can_player_reach(grid, player, (curr_i, curr_j + 1), (curr_i, curr_j), set()):
            res.append((curr_i, curr_j - 1))
        if curr_j + 1 < n and grid[curr_i][curr_j + 1] != self.WALL and self._can_player_reach(grid, player, (curr_i, curr_j - 1), (curr_i, curr_j), set()):
            res.append((curr_i, curr_j + 1))
        return res
    
    
    def _can_player_reach(self, grid, curr_pos, dst, box, visited):
        \"\"\"
        Return if player can reach dst position by doing bfs/dfs
        \"\"\"
        m, n = len(grid), len(grid[0])
        if curr_pos[0] < 0 or curr_pos[0] >= m or curr_pos[1] < 0 or curr_pos[1] >= n:
            return False
        if dst == (3, 1):
            print(curr_pos, \"ha\")
        if curr_pos == dst:
            return True
        
        for delta_i, delta_j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
            next_i, next_j = curr_pos[0] + delta_i, curr_pos[1] + delta_j
            if 0 <= next_i < m and 0 <= next_j < n:
                if grid[next_i][next_j] != self.WALL:
                    if (next_i, next_j) not in visited and (next_i, next_j) != box:
                        visited.add((next_i, next_j))
                        if self._can_player_reach(grid, (next_i, next_j), dst, box, visited):
                            return True
        return False

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        self.m = len(grid)
        self.n = len(grid[0])
        player, box = [0, 0], [0, 0]
        
        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j] == 'B':
                    box = [i, j]
                elif grid[i][j] == 'S':
                    player = [i, j]
        
        i, j = box
        x, y = player
        q = collections.deque()
        q.append((i, j, x, y))  # i, j is where the box is, x, y is where the player is
        visited = set()
        visited.add((i, j, x, y))
        
        step = 0
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        while q:
            size = len(q)
            for _ in range(size):
                i, j, x, y = q.popleft()
                if grid[i][j] == 'T':
                    return step
                
                for di, dj in dirs:
                    i2 = i + di
                    j2 = j + dj
                    if i2 < 0 or i2 >= self.m or j2 < 0 or j2 >= self.n or (i2, j2, i, j) in visited or grid[i2][j2] == '#' or not self.helper(grid, x, y, i, j, i - di, j - dj):
                        continue
                
                    q.append((i2, j2, i, j))
                    visited.add((i2, j2, i, j))
            step += 1
        
        return -1
    
    def helper(self, grid, x, y, bi, bj, i, j):
        # check if the player can go from x, y to i, j
        visited = set()
        return self.has_path(grid, x, y, bi, bj, i, j, visited)
    
    def has_path(self, grid, x, y, bi, bj, i, j, visited):
        # check if the player can go from x, y to i, j
        if x < 0 or x >= self.m or y < 0 or y >= self.n or (x == bi and y == bj) or grid[x][y] == '#' or (x, y) in visited:
            return False
        
        if x == i and y == j:
            return True
        
        visited.add((x, y))
        return self.has_path(grid, x - 1, y, bi, bj, i, j, visited) or self.has_path(grid, x + 1, y, bi, bj, i, j, visited) or self.has_path(grid, x, y + 1, bi, bj, i, j, visited) or self.has_path(grid, x, y - 1, bi, bj, i, j, visited)
        
        


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        player = box = target = None
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == \"B\":
                    box = (i, j)
                elif grid[i][j] == \"S\":
                    player = (i, j)
                elif grid[i][j] == \"T\":
                    target = (i, j)
        
        def is_valid(pos):
            r, c = pos
            if 0 <= r < rows and 0 <= c < cols:
                return grid[r][c] != \"#\"
            return False
        
        def get_distance(box):
            return abs(target[0] - box[0]) + abs(target[1] - box[1])
        
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        heap = [(get_distance(box), 0, player, box)]
        visited = set()
        
        while heap:
            distance, move, player, box = heapq.heappop(heap)
            if box == target:
                return move
            if (player, box) in visited:
                continue
            visited.add((player, box))
            for d in directions:
                next_player = (player[0] + d[0], player[1] + d[1])
                if not is_valid(next_player):
                    continue
                if box == next_player:
                    next_box = (box[0] + d[0], box[1] + d[1])
                    if not is_valid(next_box):
                        continue
                    heapq.heappush(heap, (get_distance(next_box) + move + 1, move + 1, next_player, next_box))
                else:
                    heapq.heappush(heap, (distance, move, next_player, box))
        return -1

from collections import deque

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        m, n = len(grid), len(grid[0])
        
        def Can(i, j):
            ss.add((i, j))
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0 <= x < m and 0 <= y < n and (x, y) not in ss and grid[x][y] == '.':
                    Can(x, y)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    ppl = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'B':
                    box = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    target = (i, j)
                    grid[i][j] = '.'
        
        visited = set()
        queue = deque()
        queue.append((box[0], box[1], 0, ppl[0], ppl[1]))
        ss = set()
        
        while queue:
            x, y, count, p1, p2 = queue.popleft()
            if (x, y) == target:
                return count
            ss = {(x, y)}
            Can(p1, p2)
            
            if x+1 < m and 0 <= x-1 and grid[x+1][y] == '.' and grid[x-1][y] == '.':
                if (x-1, y, x, y) not in visited and (x-1, y) in ss:
                    visited.add((x-1, y, x, y))
                    queue.append( (x+1, y, count+1, x-1, y) )
                if (x+1, y, x, y) not in visited and (x+1, y) in ss:
                    visited.add((x+1, y, x, y))
                    queue.append( (x-1, y, count+1, x+1, y) )
            
            if y+1 < n and 0 <= y-1 and grid[x][y-1] == '.' and grid[x][y+1] == '.':
                #print(\"{}.{}\".format(x, y))
                if (x, y-1, x, y) not in visited and (x, y-1) in ss:
                    visited.add((x, y-1, x, y))
                    queue.append( (x, y+1, count+1, x, y-1) )
                if (x, y+1, x, y) not in visited and (x, y+1) in ss:
                    visited.add((x, y+1, x, y))
                    queue.append( (x, y-1, count+1, x, y+1) )
            
        return -1
            


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        n, m = len(grid), len(grid[0])
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'B':
                    b = (i, j)
                if grid[i][j] == 'S':
                    s = (i, j)
                if grid[i][j] == 'T':
                    t = (i, j)
        queue = [(b[0], b[1], s[0], s[1], 0)]
        dic = {(b[0], b[1], s[0], s[1]):0}
        res = float('inf')
        while queue:
            bx, by, sx, sy, step = queue.pop(0)
            if dic[(bx, by, sx, sy)] >= res:
                continue
            if (bx, by) == t:
                res = min(res, step)
                continue
            for i in range(4):
                nsx = sx + dx[i]
                nsy = sy + dy[i]
                if not 0 <= nsx < n or not 0 <= nsy < m or grid[nsx][nsy] == '#':
                    continue
                if nsx == bx and nsy == by:
                    nbx = bx + dx[i]
                    nby = by + dy[i]
                    if (nbx, nby, nsx, nsy) in dic and dic[(nbx, nby, nsx, nsy)] <= step + 1:
                        continue
                    dic[(nbx, nby, nsx, nsy)] = step+1
                    queue.append((nbx, nby, nsx, nsy, step + 1))
                else:
                    if (bx, by, nsx, nsy) in dic and dic[(bx, by, nsx, nsy)] <= step:
                        continue
                    dic[(bx, by, nsx, nsy)] = step
                    queue.append((bx, by, nsx, nsy, step))
        return res if res != float('inf') else -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        n,m = len(grid),len(grid[0])
        B = T = S = None
        
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='B': B = (i,j)
                if grid[i][j]=='T': T = (i,j)
                if grid[i][j]=='S': S = (i,j)
                    
        #cost, B, S
        heap = [((0,B[0],B[1],S[0],S[1]))]
        heapq.heapify(heap)
        # bi,bj,si,sj
        seen = set()
        while heap:
            c,bi,bj,si,sj = heapq.heappop(heap)
            #print((bi,bj),(si,sj),c)
            if (bi,bj)==T:
                return c
            if (bi,bj,si,sj) in seen:
                continue
            seen.add((bi,bj,si,sj))
            for nsi,nsj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                if 0<=nsi<n and 0<=nsj<m and grid[nsi][nsj]!='#':
                    if (nsi,nsj)!=(bi,bj) and (bi,bj,nsi,nsj) not in seen:  
                        heapq.heappush(heap,(c,bi,bj,nsi,nsj))
                    elif (bi,bj) == (nsi,nsj) :
                        nbi,nbj = nsi-(si-nsi),nsj-(sj-nsj)
                        if 0<=nbi<n and 0<=nbj<m and (nbi,nbj,nsi,nsj) not in seen:
                            heapq.heappush(heap,(c+1,nbi,nbj,nsi,nsj))
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dire = [(1,0),(0,1),(-1,0),(0,-1)]
\t\t
        def can_get(cur_b,cur_p,tar):
            seen,cur = set([cur_p]),set([cur_p])
            while cur:
                tmp = []
                for loc in cur:
                    for x,y in dire:
                        if 0<= loc[0]+x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and (loc[0]+x,loc[1] +y) != cur_b and grid[loc[0] +x][loc[1] +y] != '#' and (loc[0]+x,loc[1] +y) not in seen:
                            tmp += [(loc[0]+x,loc[1] +y)]
                cur = set(tmp)
                seen |= cur
                if tar in seen:
                    return True
            return False
\t\t\t
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'B': box = (i,j)
                if grid[i][j] == 'S': player = (i,j)
                if grid[i][j] == 'T': target = (i,j)
\t\t\t\t
        seen,cur,res = set([(box,player)]), set([(box,player)]), 0
        while cur:
            tmp = []
            res += 1
            for b,p in cur:
                for x,y in dire:
                    if 0<= b[0]+x < len(grid) and 0 <= b[1] + y < len(grid[0]) and grid[b[0]+x][b[1]+y] != '#' and can_get(b,p,(b[0]-x,b[1]-y)) and ((b[0]+x,b[1]+y),b) not in seen:
                        tmp += [((b[0]+x,b[1]+y),b)]
            cur = set(tmp)
            seen |= cur
            for x,y in dire:
                if (target,(target[0]+x,target[1]+y)) in seen:
                    return res
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def can_get(cur_b, cur_p, tar):
            seen, cur = set([cur_p]), set([cur_p])
            while cur:
                tmp = []
                for loc in cur:
                    for x, y in dire:
                        if 0 <= loc[0] + x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and (
                            loc[0] + x, loc[1] + y) != cur_b and grid[loc[0] + x][loc[1] + y] != '#' and (
                            loc[0] + x, loc[1] + y) not in seen:
                            tmp += [(loc[0] + x, loc[1] + y)]
                cur = set(tmp)
                seen |= cur
                if tar in seen:
                    return True
            return False

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'B': box = (i, j)
                if grid[i][j] == 'S': player = (i, j)
                if grid[i][j] == 'T': target = (i, j)

        seen, cur, res = set([(box, player)]), set([(box, player)]), 0
        while cur:
            tmp = []
            res += 1
            for b, p in cur:
                for x, y in dire:
                    if 0 <= b[0] + x < len(grid) and 0 <= b[1] + y < len(grid[0]) and grid[b[0] + x][
                                b[1] + y] != '#' and can_get(b, p, (b[0] - x, b[1] - y)) and (
                    (b[0] + x, b[1] + y), b) not in seen:
                        tmp += [((b[0] + x, b[1] + y), b)]
            cur = set(tmp)
            seen |= cur
            for x, y in dire:
                if (target, (target[0] + x, target[1] + y)) in seen:
                    return res
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
                
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    man = (i, j)
                elif grid[i][j] == 'B':
                    box = (i, j)
                elif grid[i][j] == 'T':
                    target = (i, j)
        
        def validPos(loc):
            i, j = loc
            return (m > i >= 0 <= j < n) and grid[i][j] != '#'
        
        def heuristic(box):
            return abs(target[0] - box[0]) + abs(target[1] - box[1])
        
        heap = [(heuristic(box), 0, man, box)]
        seen = set()
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while heap:
            _, steps, man, box = heapq.heappop(heap)
            if box == target:
                return steps
            if (man, box) in seen:
                continue
            seen.add((man, box))
            for r, c in dirs:
                new_man = man[0] + r, man[1] + c
                if not validPos(new_man):
                    continue
                if new_man == box:
                    new_box = box[0] + r, box[1] + c
                    if not validPos(new_box):
                         continue
                    heapq.heappush(heap, (heuristic(new_box) + steps + 1, steps + 1, new_man, new_box))
                else:
                    heapq.heappush(heap, (heuristic(box) + steps, steps, new_man, box))
                    
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'T':
                    target = (i, j)
                elif grid[i][j] == 'B':
                    start_box = (i, j)
                elif grid[i][j] == 'S':
                    start_person = (i, j)
        
        def heuristic(box):
            return abs(target[0] - box[0]) + abs(target[1] - box[1])
        
        def out_bounds(location):
            i, j = location
            if i < 0 or i >= n:
                return True
            if j < 0 or j >= m:
                return True
            return grid[i][j] == '#'
        
        heap = [[heuristic(start_box), 0, start_person, start_box]]
        visited = set()
        
        while heap:
            _, moves, person, box = heapq.heappop(heap)
            if box == target:
                return moves
            if (person, box) in visited:
                continue
            visited.add((person, box))
            
            for dx, dy in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                new_person = (person[0] + dx, person[1] + dy)
                if out_bounds(new_person):
                    continue
                
                if new_person == box:
                    new_box = (box[0] + dx, box[1] + dy)
                    if out_bounds(new_box):
                        continue
                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
                else:
                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box])
        
        return -1
        
        
        
        
        
                    


\"\"\"
level 0: [bx,by,px,py]

level 1: [bx-1, by, px-1, py]

level 3: 


\"\"\"



class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        m, n = len(grid), len(grid[0])        
        bx, by, px, py = 0, 0, 0, 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    px, py = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'B':
                    bx, by = i, j
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    tx, ty = i, j
                    grid[i][j] = '.'
                
        queue = collections.deque()
        queue.append([bx, by, px, py])
        memo = collections.defaultdict(lambda : -1)
        memo[(bx, by, px, py)] = 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            bx, by, px, py = queue.popleft()
            if bx == tx and by == ty:
                return memo[(bx, by, px, py)]
                             
            for k in range(4):
                x = px + directions[k][0]
                y = py + directions[k][1]
                if x<0 or x>=m or y<0 or y>=n:
                    continue
                if grid[x][y] != '.':
                    continue
                if x == bx and y == by:
                    continue
                if memo[(bx, by, x, y)] >= 0:
                    continue
                memo[(bx, by, x, y)] = memo[(bx, by, px, py)]
                queue.appendleft([bx, by, x, y])
            
            #相邻
            if abs(px-bx) + abs(py-by) == 1:
                for k in range(4):
                    if px+directions[k][0] == bx and py+directions[k][1] == by:
                        bx2 = bx+directions[k][0]
                        by2 = by+directions[k][1]
                        if bx2<0 or bx2>=m or by2<0 or by2>=n:
                            continue
                        if grid[bx2][by2] != '.':
                            continue
                        if memo[(bx2, by2, bx, by)] >= 0:
                            continue
                        memo[(bx2, by2, bx, by)] = memo[(bx, by, px, py)] + 1
                        queue.append([bx2, by2, bx, by])
            
        return -1
            
        
        
        
        
        

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dire = [(1,0),(0,1),(-1,0),(0,-1)]
\t\t
        def can_get(cur_b,cur_p,tar):
            seen,cur = set([cur_p]),set([cur_p])
            while cur:
                tmp = []
                for loc in cur:
                    for x,y in dire:
                        if 0<= loc[0]+x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and (loc[0]+x,loc[1] +y) != cur_b and grid[loc[0] +x][loc[1] +y] != '#' and (loc[0]+x,loc[1] +y) not in seen:
                            tmp += [(loc[0]+x,loc[1] +y)]
                cur = set(tmp)
                seen |= cur
                if tar in seen:
                    return True
            return False
\t\t\t
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'B': box = (i,j)
                if grid[i][j] == 'S': player = (i,j)
                if grid[i][j] == 'T': target = (i,j)
\t\t\t\t
        seen,cur,res = set([(box,player)]), set([(box,player)]), 0
        while cur:
            tmp = set()
            res += 1
            for b,p in cur:
                for x,y in dire:
                    if 0<= b[0]+x < len(grid) and 0 <= b[1] + y < len(grid[0]) and grid[b[0]+x][b[1]+y] != '#' and can_get(b,p,(b[0]-x,b[1]-y)) and ((b[0]+x,b[1]+y),b) not in seen:
                        tmp.add(((b[0]+x,b[1]+y),b))
            cur = set(tmp)
            seen.update(cur)
            for x,y in dire:
                if (target,(target[0]+x,target[1]+y)) in seen:
                    return res
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dire = [(1,0),(0,1),(-1,0),(0,-1)]
\t\t
        def can_get(cur_b,cur_p,tar):
            seen,cur = set([cur_p]),set([cur_p])
            while cur:
                tmp = set()
                for loc in cur:
                    for x,y in dire:
                        if 0<= loc[0]+x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and (loc[0]+x,loc[1] +y) != cur_b and grid[loc[0] +x][loc[1] +y] != '#' and (loc[0]+x,loc[1] +y) not in seen:
                            tmp.add((loc[0]+x,loc[1] +y))
                cur = tmp
                seen.update(cur)
                if tar in seen:
                    return True
            return False
\t\t\t
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 'B': box = (i,j)
                if grid[i][j] == 'S': player = (i,j)
                if grid[i][j] == 'T': target = (i,j)
\t\t\t\t
        seen,cur,res = set([(box,player)]), set([(box,player)]), 0
        while cur:
            tmp = set()
            res += 1
            for b,p in cur:
                for x,y in dire:
                    if 0<= b[0]+x < len(grid) and 0 <= b[1] + y < len(grid[0]) and grid[b[0]+x][b[1]+y] != '#' and can_get(b,p,(b[0]-x,b[1]-y)) and ((b[0]+x,b[1]+y),b) not in seen:
                        tmp.add(((b[0]+x,b[1]+y),b))
            cur = tmp
            seen.update(cur)
            for x,y in dire:
                if (target,(target[0]+x,target[1]+y)) in seen:
                    return res
        return -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:

        # this loop is to get the coordinates of target, box and person. Nothing else is gained here
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == \"T\":
                    target = (i,j)
                if grid[i][j] == \"B\":
                    box = (i,j)
                if grid[i][j] == \"S\":
                    person = (i,j)

        # this function checks whether the given coordinates/indices are valid to go
        def valid(x,y):
            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'

        # this function checks whether the person can travel from current postition to destination position.
        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.
        def check(curr,dest,box):
            que = deque([curr])
            v = set()
            while que:
                pos = que.popleft()
                if pos == dest: return True
                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]
                for x,y in new_pos:
                    if valid(x,y) and (x,y) not in v and (x,y)!=box:
                        v.add((x,y))
                        que.append((x,y))
            return False

        q = deque([(0,box,person)])
        vis = {box+person}
        # this is the main bfs which gives us the answer
        while q :
            dist, box, person = q.popleft()
            if box == target: # return the distance if box is at the target
                return dist

            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).
            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]
            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates
            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]

            for new_box,new_person in zip(b_coord,p_coord): 
                # we check if the new box coordinates are valid and our current state is not in vis
                if valid(*new_box) and new_box+box not in vis:
                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates
                    if valid(*new_person) and check(person,new_person,box):
                        vis.add(new_box+box)
                        q.append((dist+1,new_box,box))

        return -1


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        #BFS. 终止条件为箱子到达目标点，或者这条路走过且有更短的走法.
        n = len(grid)
        m = len(grid[0])
        
        player = None
        box = None
        dest = None
        for i in range(n):
            for j in range(m):
                if grid[i][j] == \"B\":
                    box = (i,j)
                    grid[i][j] = \".\"
                elif grid[i][j] == \"S\":
                    player = (i,j)
                    grid[i][j] = \".\"
                elif grid[i][j] == \"T\":
                    dest = (i, j)
                    grid[i][j] = \".\"
                if player != None and box != None and dest != None:
                    break
                    
        def can_move(r, c, n, m, d, br, bc, cost):
            if r < 0 or r >= n or c < 0 or c >= m or grid[r][c] == '#':
                return False
            if (br,bc) == (r,c):
                nbr, nbc = r+d[0], c+d[1]
                br, bc = nbr, nbc
                if nbr < 0 or nbr >= n or nbc < 0 or nbc >= m or grid[nbr][nbc] == '#':
                    return False
                cost += 1
            if visited[(r,c,br,bc)] <= cost:
                return False
                
            return (br,bc, cost)
        
        visited = collections.defaultdict(lambda: float(\"inf\"))
        q = [(player[0], player[1], box[0], box[1],0)]
        res = float(\"inf\")
        while len(q)>0:
            next_q = []
            for r,c, br, bc, cost in q:
                # print(r,c, br, bc, cost, pushes)
                #看看四个方向能不能移动, 有没有箱子，有没有墙，是否走过
                dir = [(-1,0),(1,0),(0,1),(0,-1)]
                for d in dir:
                    # print(\"d\", d)
                    nr, nc = r+d[0], c+d[1]
                    move_res = can_move(nr, nc, n, m, d, br, bc, cost)
                    if move_res != False:
                        nbr, nbc, new_cost = move_res
                        visited[(nr,nc,br,bc)] = new_cost
                        #判断是否到达目的地
                        if (nbr,nbc) == dest:
                            res = min(res, new_cost)
                        else:
                            #没有到达目标才需要继续遍历
                            if (nbr,nbc) == (br,bc):
                                next_q.append((nr,nc,nbr,nbc,new_cost))
                            else:
                                next_q.append((nr,nc,nbr,nbc,new_cost))
                    else:
                        # print(\"False\", nr,nc, br, bc, cost)
                        pass
                            
            q = next_q
            
        # print(visited)
        return res if res != float(\"inf\") else -1

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        R, C = len(grid), len(grid[0])
        b_pos = s_pos = t_pos = None
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'B':
                    b_pos = (r, c)
                if grid[r][c] == 'S':
                    s_pos = (r, c)
                if grid[r][c] == 'T':
                    t_pos = (r, c)
        def is_empty(r, c):
            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'

        visited = set()
        queue = [tuple(b_pos + s_pos)]
        steps = 0
        while queue:
            new_queue = []
            for br, bc, sr, sc in queue:
                new = (br, bc, sr, sc)
                if new in visited:
                    continue
                visited.add(new)
                if (br, bc) == t_pos:
                    return steps
                for dr, dc in dirs:
                    nsr, nsc = dr + sr, dc + sc
                    if (nsr, nsc) == (br, bc):
                        nbr, nbc = dr + br, dc + bc
                        box_move = True
                    else:
                        nbr, nbc = br, bc
                        box_move = False
                    if not is_empty(nsr, nsc) or not is_empty(nbr, nbc):
                        continue
                    new = (nbr, nbc, nsr, nsc)
                    if box_move:
                        new_queue.append(new)
                    else:
                        queue.append(new)
            queue = new_queue
            steps += 1
        return -1

import heapq
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='S':
                    s=(i,j)
                if grid[i][j]=='B':
                    b=(i,j)
                if grid[i][j]=='T':
                    t=(i,j)
        def valid(i,j,s=None,b=None):
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):
                return False
            if grid[i][j]=='#':
                return False
            if s is not None:
                if (i,j)==s:
                    return False
            if b is not None:
                if (i,j)==b:
                    return False
            return True
        def next_state(s,b,step):
            for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:
                if valid(s[0]+di,s[1]+dj):
                    if b==(s[0]+di,s[1]+dj) and valid(b[0]+di,b[1]+dj):
                        nxt_s,nxt_b,nxt_step=b,(b[0]+di,b[1]+dj),step+1
                    else:
                        nxt_s=(s[0]+di,s[1]+dj)
                        nxt_b,nxt_step=b,step
                    yield nxt_s,nxt_b,nxt_step
        def edit_dis(s,b):
            return abs(s[0]-b[0])+abs(s[1]-b[1])
        def search(s,b):
            q=[(0,edit_dis(s,b),s,b)]
            visited={}
            visited[(s,b)]=0
            while q:
                (step,_,s,b)=heapq.heappop(q)
                if b==t:
                    return step
                for nxt_s,nxt_b,nxt_step in next_state(s,b,step):
                    if (nxt_s,nxt_b) not in visited or visited[(nxt_s,nxt_b)]>nxt_step:
                        q.append((nxt_step,edit_dis(nxt_s,nxt_b),nxt_s,nxt_b))
                        visited[(nxt_s,nxt_b)]=nxt_step
            return -1
        return search(s,b)
                        


import heapq
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='S':
                    s=(i,j)
                if grid[i][j]=='B':
                    b=(i,j)
                if grid[i][j]=='T':
                    t=(i,j)
        def valid(i,j,s=None,b=None):
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):
                return False
            if grid[i][j]=='#':
                return False
            if s is not None:
                if (i,j)==s:
                    return False
            if b is not None:
                if (i,j)==b:
                    return False
            return True
        def next_state(s,b,step):
            for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:
                if valid(s[0]+di,s[1]+dj):
                    if b==(s[0]+di,s[1]+dj) and valid(b[0]+di,b[1]+dj):
                        nxt_s,nxt_b,nxt_step=b,(b[0]+di,b[1]+dj),step+1
                    else:
                        nxt_s=(s[0]+di,s[1]+dj)
                        nxt_b,nxt_step=b,step
                    yield nxt_s,nxt_b,nxt_step
        def edit_dis(s,b):
            return abs(s[0]-b[0])+abs(s[1]-b[1])
        def search(s,b):
            q=[(0,s,b)]
            visited={}
            visited[(s,b)]=0
            while q:
                (step,s,b)=heapq.heappop(q)
                if b==t:
                    return step
                for nxt_s,nxt_b,nxt_step in next_state(s,b,step):
                    if (nxt_s,nxt_b) not in visited or visited[(nxt_s,nxt_b)]>nxt_step:
                        q.append((nxt_step,nxt_s,nxt_b))
                        visited[(nxt_s,nxt_b)]=nxt_step
            return -1
        return search(s,b)
                        


class Solution:
    def init_positions(self):
        for i in range(self.m):
            for j in range(self.n):
                if self.grid[i][j] == 'S':
                    pusher = i, j
                if self.grid[i][j] == 'B':
                    box = i, j
                if self.grid[i][j] == 'T':
                    target = i, j
        return pusher, box, target
        
    def bfs_from_pusher(self, pusher, box):
        visited = set()
        frontier = {pusher}
        while frontier:
            visited |= frontier
            new_frontier = set()
            for pos in frontier:
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    new_x, new_y = pos[0] + dx, pos[1] + dy
                    if (0 <= new_x < self.m and 0 <= new_y < self.n and
                        self.grid[new_x][new_y] != '#' and (new_x, new_y) != box and
                        (new_x, new_y) not in visited):
                        new_frontier.add((new_x, new_y))
            frontier = new_frontier
        return visited
    
    def reachable_neighbors_of(self, box, visited):
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_x, new_y = box[0] + dx, box[1] + dy
            if (new_x, new_y) in visited:
                mir_x, mir_y = (2 * box[0] - new_x), (2 * box[1] - new_y)
                if 0 <= mir_x < self.m and 0 <= mir_y < self.n and self.grid[mir_x][mir_y] != '#':
                    yield mir_x, mir_y
                        
    def minPushBox(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0])
        pusher, box, target = self.init_positions()
        
        frontier = {(box, pusher)}
        visited = set()
        dist = 0
        while frontier:
            visited |= frontier
            for box, _ in visited:
                if box == target:
                    return dist
            
            new_frontier = set()
            for cur_box, cur_pusher in frontier:
                visited_pusher = self.bfs_from_pusher(cur_pusher, cur_box)
                for new_box in self.reachable_neighbors_of(cur_box, visited_pusher):
                    if (new_box, cur_box) not in visited:
                        new_frontier.add((new_box, cur_box))
            frontier = new_frontier
            dist += 1
        return -1