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:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n, g = len(grid), len(grid[0]), collections.defaultdict(list)\n        for i in range(m):\n            for j in range(n):\n                g[grid[i][j]] += [complex(i, j)]\n        \n        def f(b, s):\n            nonlocal time\n            time += 1\n            boxToTarget = b - target\n            return (abs((boxToTarget.real))+abs((boxToTarget).imag)+s, abs(boxToTarget), time)\n        \n        player, box, target, time = *g['S'], *g['B'], *g['T'], 1\n        floor = {player, box, target, *g['.']}\n        \n        alpha = [(f(box, 1), 1, player, box)]\n        directions, visited = (1, -1, 1j, -1j), set()   # \u4e0b\u4e0a\u53f3\u5de6\n        \n        # \u56e0\u4e3a\u90fd\u4e0d\u662f\u6570\u800c\u662f\u590d\u6570\u3002\u56e0\u6b64\u91c7\u7528\u5b57\u5178\u6620\u5c04\u7684\u65b9\u5f0f\u5b9a\u4e49low dfn\n        low = dict.fromkeys(floor, 0)  # \u6807\u51c6\u7684dict.fromkeys\u521b\u5efa\u5b57\u5178\u3002keys\u6765\u6e90\u7b2c\u4e00\u4e2a\u53c2\u6570\u7b2c\u4e8c\u4e2a\u53c2\u6570\u9ed8\u8ba4\u6216\u8d4b\u503c\n        dfn = low.copy()\n        count = 0\n        index = {}\n        # \u6807\u51c6\u65e0\u5411\u56fetarjan\u6df1\u5ea6\u4f18\u5148\u6269\u5c55\u51fd\u6570\uff0c\u53c2\u6570currIndex\u4e3a\u5f53\u524d\u62d3\u5c55\u70b9\uff0c\u8bb0\u5f55\u62d3\u5c55\u7684\u7236\u8282\u70b9\u9632\u6b62\u91cd\u590d\u62d3\u5c55\n        def tarjan(currIndex, parentIndex):\n            nonlocal count\n            count += 1\n            dfn[currIndex] = low[currIndex] = count\n            index[count] = currIndex\n            for direction in directions:\n                nextIndex = currIndex + direction\n                if nextIndex in floor and nextIndex != parentIndex:\n                    if not low[nextIndex]:\n                        tarjan(nextIndex, currIndex)\n                    low[currIndex] = min(low[currIndex], low[nextIndex])\n        \n        #\u8fd0\u884ctarjan\u51fd\u6570\uff0c\u521d\u59cb\u503c\u4e3abox\u7684\u5750\u6807\uff0c\u56e0\u4e3a\u5750\u6807\u90fd\u5728\u590d\u5e73\u9762\u7b2c\u4e00\u8c61\u9650\uff0c\u521d\u59cb\u7236\u8282\u70b9\u53d6-1\u4e0d\u5f71\u54cd\u8ba1\u7b97\n        tarjan(box, -1)\n        #print(low)\n        #print(dfn)\n        # \u5982\u679c\u7bb1\u5b50\u5728\u5272\u70b9\u4e0a\u4ecd\u53ef\u4ee5\u79fb\u52a8\u7684\u8bdd\uff0c\u5219\u7bb1\u5b50\u5728\u79fb\u52a8\u7684\u8fc7\u7a0b\u4e2d\uff0c\u4eba\u7684\u5750\u6807\u4e5f\u5b8c\u6210\u4e86\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u8f6c\u79fb\uff0c\n        # \u6240\u4ee5\u5373\u4fbf\u662f\u5bbd\u5ea6\u4e3a1\u7684\u788e\u7247\u5316\u7684\u5f3a\u8fde\u901a\u5206\u91cf\u96a7\u9053\uff0c\u4e5f\u4e0d\u5f71\u54cd\u4e0a\u8ff0\u7ed3\u8bba\u3002\n        for currIndex in floor:  # \u6240\u6709\u7684\u53ef\u8fbe\u70b9\n            connect = [currIndex]\n            while dfn[connect[-1]] != low[connect[-1]]:\n                connect.append(index[low[connect[-1]]])\n            for w in connect[:-2]:\n                low[w] = low[connect[-1]]\n        #print(low)\n        \n        # \u8ba1\u7b97\u5b8c\u5f3a\u8fde\u901a\u5206\u91cf\u540e\u53ef\u4ee5\u52a0\u4e00\u4e2a\u526a\u679d\uff0c\u5373\u5982\u679c\u4eba\u6216\u76ee\u6807\u70b9\u6ca1\u88ab\u8ba1\u7b97\u5230\uff0c\u5219\u8868\u793a\u4e09\u4e2a\u5173\u952e\u70b9\u4e0d\u5728\u540c\u4e00\u4e2a\u5e76\u67e5\u96c6\u91cc\u9762\uff0c\n        # \u53ef\u4ee5\u76f4\u63a5\u8fd4\u56de-1\n        if not low[player] * low[target]:\n            return -1\n        \n        while alpha:\n            _, steps, currPlayer, currBox = heapq.heappop(alpha)\n            for direction in directions:\n                nextPlayer, nextBox = currBox - direction, currBox + direction\n                if nextBox in floor and nextPlayer in floor and (nextPlayer, currBox) not in visited and low[currPlayer] == low[nextPlayer]:\n                    if nextBox == target:\n                        return steps\n                    heapq.heappush(alpha, (f(nextBox, steps + 1), steps + 1, currBox, nextBox))\n                    visited.add((nextPlayer, currBox))\n        return -1", "\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n, g = len(grid), len(grid[0]), collections.defaultdict(list)\n        for i in range(m):\n            for j in range(n):\n                g[grid[i][j]] += [complex(i, j)]\n        \n        def f(b, s):\n            nonlocal time\n            time += 1\n            boxToTarget = b - target\n            return (abs((boxToTarget.real))+abs((boxToTarget).imag)+s, abs(boxToTarget), time)\n        \n        player, box, target, time = *g['S'], *g['B'], *g['T'], 1\n        floor = {player, box, target, *g['.']}\n        \n        alpha = [(f(box, 1), 1, player, box)]\n        directions, visited = (1, -1, 1j, -1j), set()   # \u4e0b\u4e0a\u53f3\u5de6\n        \n        # \u56e0\u4e3a\u90fd\u4e0d\u662f\u6570\u800c\u662f\u590d\u6570\u3002\u56e0\u6b64\u91c7\u7528\u5b57\u5178\u6620\u5c04\u7684\u65b9\u5f0f\u5b9a\u4e49low dfn\n        low = dict.fromkeys(floor, 0)  # \u6807\u51c6\u7684dict.fromkeys\u521b\u5efa\u5b57\u5178\u3002keys\u6765\u6e90\u7b2c\u4e00\u4e2a\u53c2\u6570\u7b2c\u4e8c\u4e2a\u53c2\u6570\u9ed8\u8ba4\u6216\u8d4b\u503c\n        dfn = low.copy()\n        count = 0\n        index = {}\n        # \u6807\u51c6\u65e0\u5411\u56fetarjan\u6df1\u5ea6\u4f18\u5148\u6269\u5c55\u51fd\u6570\uff0c\u53c2\u6570currIndex\u4e3a\u5f53\u524d\u62d3\u5c55\u70b9\uff0c\u8bb0\u5f55\u62d3\u5c55\u7684\u7236\u8282\u70b9\u9632\u6b62\u91cd\u590d\u62d3\u5c55\n        def tarjan(currIndex, parentIndex):\n            nonlocal count\n            count += 1\n            dfn[currIndex] = low[currIndex] = count\n            index[count] = currIndex\n            for direction in directions:\n                nextIndex = currIndex + direction\n                if nextIndex in floor and nextIndex != parentIndex:\n                    if not low[nextIndex]:\n                        tarjan(nextIndex, currIndex)\n                    low[currIndex] = min(low[currIndex], low[nextIndex])\n        \n        #\u8fd0\u884ctarjan\u51fd\u6570\uff0c\u521d\u59cb\u503c\u4e3abox\u7684\u5750\u6807\uff0c\u56e0\u4e3a\u5750\u6807\u90fd\u5728\u590d\u5e73\u9762\u7b2c\u4e00\u8c61\u9650\uff0c\u521d\u59cb\u7236\u8282\u70b9\u53d6-1\u4e0d\u5f71\u54cd\u8ba1\u7b97\n        tarjan(box, -1)\n        #print(low)\n        #print(dfn)\n        # \u5982\u679c\u7bb1\u5b50\u5728\u5272\u70b9\u4e0a\u4ecd\u53ef\u4ee5\u79fb\u52a8\u7684\u8bdd\uff0c\u5219\u7bb1\u5b50\u5728\u79fb\u52a8\u7684\u8fc7\u7a0b\u4e2d\uff0c\u4eba\u7684\u5750\u6807\u4e5f\u5b8c\u6210\u4e86\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u8f6c\u79fb\uff0c\n        # \u6240\u4ee5\u5373\u4fbf\u662f\u5bbd\u5ea6\u4e3a1\u7684\u788e\u7247\u5316\u7684\u5f3a\u8fde\u901a\u5206\u91cf\u96a7\u9053\uff0c\u4e5f\u4e0d\u5f71\u54cd\u4e0a\u8ff0\u7ed3\u8bba\u3002\n        for currIndex in floor:  # \u6240\u6709\u7684\u53ef\u8fbe\u70b9\n            connect = [currIndex]\n            while dfn[connect[-1]] != low[connect[-1]]:\n                connect.append(index[low[connect[-1]]])\n            for w in connect[:-2]:\n                low[w] = low[connect[-1]]\n        #print(low)\n        \n        # \u8ba1\u7b97\u5b8c\u5f3a\u8fde\u901a\u5206\u91cf\u540e\u53ef\u4ee5\u52a0\u4e00\u4e2a\u526a\u679d\uff0c\u5373\u5982\u679c\u4eba\u6216\u76ee\u6807\u70b9\u6ca1\u88ab\u8ba1\u7b97\u5230\uff0c\u5219\u8868\u793a\u4e09\u4e2a\u5173\u952e\u70b9\u4e0d\u5728\u540c\u4e00\u4e2a\u5e76\u67e5\u96c6\u91cc\u9762\uff0c\n        # \u53ef\u4ee5\u76f4\u63a5\u8fd4\u56de-1\n        if not low[player] * low[target]:\n            return -1\n        \n        while alpha:\n            _, steps, currPlayer, currBox = heapq.heappop(alpha)\n            for direction in directions:\n                nextPlayer, nextBox = currBox - direction, currBox + direction\n                if nextBox in floor and nextPlayer in floor and (nextPlayer, currBox) not in visited and low[currPlayer] == low[nextPlayer]:\n                    if nextBox == target:\n                        return steps\n                    heapq.heappush(alpha, (f(nextBox, steps + 1), steps + 1, currBox, nextBox))\n                    visited.add((nextPlayer, currBox))\n        return -1\n\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n\n        # this loop is to get the coordinates of target, box and person. Nothing else is gained here\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i,j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i,j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i,j)\n\n        # this function checks whether the given coordinates/indices are valid to go\n        def valid(x,y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'\n\n        # this function checks whether the person can travel from current postition to destination position.\n        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.\n        def check(curr,dest,box):\n            que = deque([curr])\n            v = set()\n            while que:\n                pos = que.popleft()\n                if pos == dest: return True\n                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]\n                for x,y in new_pos:\n                    if valid(x,y) and (x,y) not in v and (x,y)!=box:\n                        v.add((x,y))\n                        que.append((x,y))\n            return False\n\n        q = deque([(0,box,person)])\n        vis = {box+person}\n        # this is the main bfs which gives us the answer\n        while q :\n            dist, box, person = q.popleft()\n            if box == target: # return the distance if box is at the target\n                return dist\n\n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n\n            for new_box,new_person in zip(b_coord,p_coord): \n                # we check if the new box coordinates are valid and our current state is not in vis\n                if valid(*new_box) and new_box+box not in vis:\n                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates\n                    if valid(*new_person) and check(person,new_person,box):\n                        vis.add(new_box+box)\n                        q.append((dist+1,new_box,box))\n\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        num_rows = len(grid)\n        num_cols = len(grid[0])\n        for r in range(num_rows):\n            for c in range(num_cols):\n                if grid[r][c] == 'T':\n                    target_row, target_col = r, c\n                    grid[r][c] = '.'\n                elif grid[r][c] in 'B':\n                    box_row, box_col = r, c\n                    grid[r][c] = '.'\n                elif grid[r][c] in 'S':\n                    src_row, src_col = r, c\n                    grid[r][c] = '.'\n        def traversal(player_row, player_col, box_row, box_col, visited):\n            if not (0 <= player_row < num_rows and 0 <= player_col < num_cols):\n                return visited\n            if grid[player_row][player_col] != '.' or (player_row, player_col) in visited:\n                return visited\n            visited.add((player_row, player_col))\n            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n                new_player_row = player_row + i\n                new_player_col = player_col + j\n                if new_player_row != box_row or new_player_col != box_col:\n                    traversal(new_player_row, new_player_col, box_row, box_col, visited)\n            return visited\n        queue = deque([(src_row, src_col, box_row, box_col, 0)])\n        visited = {(src_row, src_col, box_row, box_col)}\n        while queue:\n            curr_row, curr_col, box_row, box_col, num_pushs = queue.popleft()\n            reachable = traversal(curr_row, curr_col, box_row, box_col, set())\n            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n                new_box_row = box_row+i\n                new_box_col = box_col+j\n                if not (0 <= new_box_row < num_rows and 0 <= new_box_col < num_cols):\n                    continue\n                if grid[new_box_row][new_box_col] != '.':\n                    continue\n                if (box_row - i, box_col - j) in reachable and (box_row, box_col, new_box_row, new_box_col) not in visited:\n                    visited.add((box_row, box_col, new_box_row, new_box_col))\n                    if new_box_row == target_row and new_box_col == target_col:\n                        return num_pushs + 1\n                    queue.append((box_row, box_col, new_box_row, new_box_col, num_pushs + 1))\n        return -1\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        def move(node, dx, dy):\n            px, py, bx, by, dist = node\n            px += dx\n            py += dy\n            illegal = (-1, -1, -1, -1, -1)\n            if px < 0 or px >= m or py < 0 or py >= n or grid[px][py] == \\\"#\\\":\n                return illegal\n            if px == bx and py == by:\n                bx += dx\n                by += dy\n                if bx < 0 or bx >= m or by < 0 or by >= n or grid[bx][by] == \\\"#\\\":\n                    return illegal\n                return (px, py, bx, by, dist+1)\n            if grid[px][py] == \\\".\\\":\n                return (px, py, bx, by, dist)\n        \n        player, target, box = [], [], []\n        for r in range(m):\n            for c in range(n):\n                if grid[r][c] == \\\"S\\\":\n                    player = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"T\\\":\n                    target = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"B\\\":\n                    box = (r, c)\n                    grid[r][c] = \\\".\\\"\n        \n        queue = collections.deque()\n        queue.append((player[0], player[1], box[0], box[1], 0))\n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n        res = float(\\\"inf\\\")\n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                node = queue.popleft()\n                px, py, bx, by, dist = node\n                if (bx, by) == target:\n                    res = min(res, dist)\n                if dist < visited[(px, py, bx, by)]:\n                    visited[(px, py, bx, by,)] = dist\n                else:\n                    continue\n                for dx, dy in directions:\n                    newNode = move(node, dx, dy)\n                    px2, py2, bx2, by2, dist2 = newNode\n                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:\n                        queue.append(newNode)\n                    \n        \n        return res if res < float(\\\"inf\\\") else -1\n    \n    \n    \n    \n    \n    \n        \n        \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        nrow, ncol = len(grid), len(grid[0])\n        \n        def move(tup, d):\n            roffset, coffset = d\n            pr,pc,br,bc,dist = tup\n            pr += roffset\n            pc += coffset\n            illegal = (-1,-1,-1,-1,-1)\n            if pr<0 or pr>=nrow or pc<0 or pc>= ncol or grid[pr][pc]==\\\"#\\\":\n                return illegal\n            if pr==br and pc==bc:\n                br += roffset\n                bc += coffset\n                if br<0 or br>=nrow or bc<0 or bc>=ncol or grid[br][bc]==\\\"#\\\":\n                    return illegal\n                return (pr,pc,br,bc,dist+1)\n            if grid[pr][pc] == \\\".\\\":\n                return (pr,pc,br,bc,dist)\n        \n        p,t,b = [],[],[]\n        for r in range(nrow):\n            for c in range(ncol):\n                if grid[r][c] == \\\"S\\\":\n                    p = (r,c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"T\\\":\n                    t = (r,c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"B\\\":\n                    b = (r,c)\n                    grid[r][c] = \\\".\\\"\n                    \n        q = collections.deque()\n        q.append((p[0],p[1],b[0],b[1],0))\n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        ret = float(\\\"inf\\\")\n        while q:\n            for _ in range(len(q)):\n                tup = q.popleft()\n                pr,pc,br,bc,dist = tup\n                if (br,bc) == t:\n                    ret = min(ret, dist)\n                if dist < visited[(pr,pc,br,bc)]:\n                    visited[(pr,pc,br,bc)] = dist\n                else:\n                    continue\n                for d in [(-1,0),(1,0),(0,1),(0,-1)]:\n                    tup2 = move(tup, d)\n                    pr2,pc2,br2,bc2,dist2 = tup2\n                    if pr2 != -1 and dist2 < visited[(pr2,pc2,br2,bc2)]:\n                        q.append(tup2)\n        return ret if ret < float(\\\"inf\\\") else -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        queue = deque()\n        m = len(grid)\n        n = len(grid[0])\n        visited = {}\n        \n        rq = deque()\n        reach = {}\n        startx, starty  = -1,-1\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    rq.append([i,j])\n                    startx, starty = i,j   \n        \n                    \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    queue.append([i,j, 0, startx, starty])\n                    visited[(i,j, startx, starty)] = 1       \n                    \n        \n        while(len(queue) > 0):\n            x, y,  step, startx, starty = queue.popleft()\n            \n            #print(x, y, step, grid[x][y])\n            if grid[x][y] == 'T':\n                return step\n\n            rq = deque()\n            reach = {}\n            rq.append([startx, starty])\n            while(len(rq) > 0):\n                rx, ry = rq.popleft()\n                reach[(rx, ry)] = 1\n                for deltax, deltay in [[-1,0],[1,0],[0,-1],[0,1]]:\n                    nx, ny = rx+deltax, ry+deltay\n                    if nx >= 0 and nx<m and ny >=0 and ny < n:\n                        if grid[nx][ny] != '#' and (nx,ny) != (x,y)  and (nx,ny) not in reach:\n                            rq.append([nx,ny])\n                            reach[(nx,ny)] = 1\n            \n            \n            \n            for deltax, deltay in [[-1,0],[1,0],[0,-1],[0,1]]:\n                nx, ny = x + deltax, y + deltay\n                otherx, othery = x-deltax, y-deltay\n                \n                if nx >= 0 and nx<m and ny >=0 and ny < n and otherx >=0 and otherx <m and othery >=0 and othery < n:\n                    if grid[nx][ny] != '#' and grid[otherx][othery] != '#':\n                        if (nx, ny,otherx, othery) not in visited and (otherx,othery) in reach:\n                            queue.append([nx, ny, step+1, otherx, othery])\n                            visited[(nx,ny,otherx, othery)] = 1\n            \n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        rows, cols = len(grid), len(grid[0])\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == 'T':\n                    target = (r,c)\n                if grid[r][c] == 'S':\n                    start_person = (r,c)\n                if grid[r][c] == 'B':\n                    start_box = (r,c)\n            \n        def heuristic(box):\n            return abs(target[0]-box[0]) + abs(target[1]-box[1])\n\n        def out_bounds(location):\n            r,c=location\n            return r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == '#'\n\n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        vis = set()\n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n            if (person, box) in vis:\n                continue\n            vis.add((person, box))\n\n            for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:\n                new_person = (person[0]+dr,person[1]+dc)\n                if out_bounds(new_person):\n                    continue\n\n                if new_person == box:\n                    new_box = (box[0]+dr, box[1]+dc)\n                    if out_bounds(new_box):\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box)+moves+1, moves+1, new_person, new_box])\n                else:\n                    heapq.heappush(heap, [heuristic(box)+moves, moves, new_person, box])\n\n        return -1\n                        \n                    \n                    \n                    \n                    \n", "import heapq\n\ndef valid(grid, r, c):\n    max_r, max_c = len(grid)-1, len(grid[0])-1\n    \n    if 0 <= r <= max_r and 0 <= c <= max_c and grid[r][c] != \\\"#\\\":\n        return True\n    \n    return False\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        for r in range(len(grid)):\n            for c in range(len(grid[0])):\n                if grid[r][c] == \\\"S\\\":\n                    s_r, s_c = r, c\n                if grid[r][c] == \\\"B\\\":\n                    b_r, b_c = r,c\n                if grid[r][c] == \\\"T\\\":\n                    target = (r,c)\n        \n        min_queue = [(0, s_r, s_c, b_r, b_c)]\n        visited = set()\n        directions = ((1,0), (-1, 0), (0,1), (0,-1))\n        \n        while len(min_queue) > 0:\n            cost, s_r, s_c, b_r, b_c = heapq.heappop(min_queue)\n            \n            if (b_r, b_c) == target:\n                return cost\n            \n            if (s_r, s_c, b_r, b_c) in visited:\n                continue\n                \n            visited.add((s_r, s_c, b_r, b_c))\n            \n            for dr, dc in directions:\n                new_cost = cost\n                ns_r, ns_c = s_r + dr, s_c + dc\n                nb_r, nb_c = b_r, b_c\n                \n                if (ns_r, ns_c) == (nb_r, nb_c):\n                    new_cost +=1\n                    nb_r, nb_c = nb_r + dr, nb_c + dc\n                    \n                new_state = (ns_r, ns_c, nb_r, nb_c)\n                \n                if valid(grid, ns_r, ns_c) and valid(grid, nb_r, nb_c) and new_state not in visited:\n                    heapq.heappush(min_queue, (new_cost, *new_state))\n                \n        return -1\n                ", "from queue import deque\n\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        def isValid(pos):\n            i, j = pos[0], pos[1]\n            return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] != '#'\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'T':\n                    target = (i, j)\n                elif grid[i][j] == 'B':\n                    box = (i, j)\n                elif grid[i][j] == 'S':\n                    player = (i, j)\n\n        def personCanMove(pos, dest, box):\n            que = deque([pos])\n            seen = {pos}\n            while que:\n                p = que.popleft()\n                if p == dest:\n                    return True\n                i, j = p[0], p[1]\n                nextPos = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]\n                for nextI, nextJ in nextPos:\n                    if isValid((nextI, nextJ)) and (nextI, nextJ) not in seen and (nextI, nextJ) != box:\n                        seen.add((nextI, nextJ))\n                        que.append((nextI, nextJ))\n            return False\n        q = deque([(box, player, 0)])\n        seen = {box + player}\n        while q:\n            b, p, pushes = q.popleft()\n            if b == target:\n                return pushes\n            nextBArr = [(b[0]-1, b[1]), (b[0]+1, b[1]),\n                        (b[0], b[1]+1), (b[0], b[1]-1)]\n            pushPosArr = [(b[0]+1, b[1]), (b[0]-1, b[1]),\n                          (b[0], b[1]-1), (b[0], b[1]+1)]\n            for nextB, pushPos in zip(nextBArr, pushPosArr):\n                if isValid(nextB) and nextB+b not in seen:\n                    if isValid(pushPos) and personCanMove(p, pushPos, b):\n                        q.append((nextB, b, pushes + 1))\n                        seen.add(nextB + b)\n        return -1\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        if not grid or not grid[0]:\n            return -1\n        \n        # Main idea: run Dijkstra's except only expand on nodes\n        # that do not have a wall on the oposite side of the\n        # box location.\n        self.grid = grid\n        dst = None\n        start = None\n        box_start = None\n        from queue import PriorityQueue\n        pq = PriorityQueue()\n        for row in range(len(grid)):\n            for col in range(len(grid[row])):\n                elem = grid[row][col]\n                if elem == \\\"B\\\":\n                    box_start = (row, col)\n                elif elem == \\\"T\\\":\n                    dst = (row, col)\n                elif elem == \\\"S\\\":\n                    start = (row, col)\n        \n        assert dst is not None\n        assert start is not None\n        assert box_start is not None\n        pq.put((0, box_start[0], box_start[1], start))\n        \n        best = {}\n        while not pq.empty():\n            pushes, row, col, start = pq.get()\n            if (row, col, start) not in best or best.get((row, col, start), float(\\\"inf\\\")) > pushes:\n                best[(row, col, start)] = pushes\n                if (row, col) == dst:\n                    return pushes\n                if row + 1 < len(grid) and row - 1 >= 0:\n                    if grid[row + 1][col] != \\\"#\\\" and grid[row - 1][col] != \\\"#\\\" and self.dfs(start[0], start[1], (row +1, col), set(), (row, col)):\n                        pq.put((pushes + 1, row - 1, col, (row, col)))\n                    if grid[row - 1][col] != \\\"#\\\" and grid[row + 1][col] != \\\"#\\\" and self.dfs(start[0], start[1], (row - 1, col), set(), (row, col)):\n                        pq.put((pushes + 1, row + 1, col, (row, col)))\n                if col + 1 < len(grid[0]) and col - 1 >= 0:\n                    if grid[row][col + 1] != \\\"#\\\" and grid[row][col - 1] != \\\"#\\\" and self.dfs(start[0], start[1], (row , col + 1), set(), (row, col)):\n                        pq.put((pushes + 1, row, col - 1, (row, col)))\n                    if grid[row][col - 1] != \\\"#\\\" and grid[row][col + 1] != \\\"#\\\" and self.dfs(start[0], start[1], (row , col - 1), set(), (row, col)):\n                        pq.put((pushes + 1, row, col + 1, (row, col)))\n        return -1\n    \n    def dfs(self, r, c, goal, seen, box_location):\n        if (r, c) == goal:\n            return True\n        if not (0 <= r < len(self.grid)):\n            return False\n        if not (0 <= c < len(self.grid[0])):\n            return False\n        if self.grid[r][c] == \\\"#\\\":\n            return False\n        if (r, c) == box_location:\n            return False\n        if (r, c) not in seen:\n            seen.add((r, c))\n            if self.dfs(r + 1, c, goal, seen, box_location):\n                return True\n            if self.dfs(r - 1, c, goal, seen, box_location):\n                return True\n            if self.dfs(r, c + 1, goal, seen, box_location):\n                return True\n            if self.dfs(r, c - 1, goal, seen, box_location):\n                return True\n        return False", "from collections import deque\ndirections = [[0,-1], [0,1], [-1, 0], [1,0]]\ndef can_move(source,dest, a, walls, box):\n    q = deque()\n    q.append(source)\n    visited = set()\n    while q:\n        item = q.popleft()\n        if item == dest:\n            return True\n        if item in visited:\n            continue\n        visited.add(item)\n        for direction in directions:\n            new_item = (item[0]+direction[0], item[1]+direction[1])\n            if is_valid(a, new_item, walls, box):\n                q.append(new_item)\n                \ndef is_valid(a, pos,walls,box=''):\n    x, y = pos\n    if 0<=x<len(a) and  0<=y<len(a[0]) and  (x,y) not in walls and (x,y) != box:\n        return True\n    return False\n    \n    \n        \ndef get_info(a):\n    walls=set()\n    for i in range(len(a)):\n        for j in range(len(a[0])):\n            if a[i][j] == '#':\n                walls.add((i,j))\n            if a[i][j] == 'S':\n                person = (i,j)\n            if a[i][j] == 'T':\n                target = (i,j)\n            if a[i][j] == 'B':\n                box = (i,j)\n    return person, target, box, walls\n\ndef get_min_moves(a):\n    person, target, box, walls = get_info(a)\n    q = deque()\n    q.append((0, box, person))\n    result = float('inf')\n    visited = set()\n    while q:\n        dist, box, person = q.popleft()\n        if (box,person) in visited:\n            continue\n        visited.add((box,person))\n        if box == target:\n            result =min(result, dist)\n            continue\n        for direction in directions:\n            new_player_position  = (box[0] +direction[0], box[1] +direction[1])\n            new_box = (box[0] +direction[0]*-1, box[1] +direction[1]*-1) \n            if is_valid(a, new_box, walls) and can_move(person, new_player_position, a, walls, box):\n                if is_valid(a,new_player_position, walls):\n                    q.append((dist + 1, new_box, box))\n    return result if result != float('inf') else -1\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        return get_min_moves(grid)", "import heapq\n\nclass Solution:\n  def minPushBox(self, grid: List[List[str]]) -> int:\n    # bfs, dfs, a-star search\n    # key:\n    # represent the state using (xb, yb, xp, yp), box and storekeeper coordinates, where storekeeper can move around,\n    # up down left and right, and push the box when storekeeper move to box position and the cell next to it is empty.\n    m, n = len(grid), len(grid[0])\n    xb, yb, xs, ys, xt, yt = -1, -1, -1, -1, -1, -1\n    for x in range(m):\n      for y in range(n):\n        if grid[x][y] == 'B':\n          xb, yb = x, y\n          grid[x][y] = '.'\n        if grid[x][y] == 'S':\n          xs, ys = x, y\n          grid[x][y] = '.'\n        if grid[x][y] == 'T':\n          xt, yt = x, y\n          grid[x][y] = '.'\n    # a-star search\n    # heuristic: h(box, target) = abs(xb - xt) + abs(yb - yt), as the lower bound of moves to push box to target.\n    # init\n    q, seen = [(abs(xb - xt) + abs(yb - yt) + 0, 0, xb, yb, xs, ys)], set()\n    while q:\n      h, d, xb, yb, xs, ys = heapq.heappop(q)\n      if (xb, yb) == (xt, yt):\n        return d\n      if (xb, yb, xs, ys) not in seen:\n        seen.add((xb, yb, xs, ys))\n        # storekeeper moves around and pushes the box when step into box coordinates\n        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n          xr, yr = xs + dx, ys + dy\n          if 0 <= xr < m and 0 <= yr < n and grid[xr][yr] == '.':\n            if (xr, yr) == (xb, yb):\n              xc, yc = xb + dx, yb + dy\n              if 0 <= xc < m and 0 <= yc < n and grid[xc][yc] == '.':\n                heapq.heappush(q, (abs(xc - xt) + abs(yc - yt) + d + 1, d + 1, xc, yc, xr, yr))\n            else:\n              heapq.heappush(q, (h, d, xb, yb, xr, yr))\n    return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        rows, cols = len(grid), len(grid[0])\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == \\\"T\\\":\n                    target = (r, c)\n                if grid[r][c] == \\\"B\\\":\n                    start_box = (r, c)\n                if grid[r][c] == \\\"S\\\":\n                    start_person = (r, c)\n                    \n        def heuristic(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n        \n        def out_bounds(location):  # return whether the location is in the grid and not a wall\n            r, c = location\n            if r < 0 or r >= rows:\n                return True\n            if c < 0 or c >= cols:\n                return True\n            return grid[r][c] == \\\"#\\\"\n                        \n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        visited = set()\n        \n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n            if (person, box) in visited: # do not visit same state again\n                continue\n            visited.add((person, box))\n            \n            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:\n                new_person = (person[0] + dr, person[1] + dc)\n                if out_bounds(new_person):\n                    continue\n                    \n                if new_person == box:\n                    new_box = (box[0] + dr, box[1] + dc)\n                    if out_bounds(new_box):\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])\n                else:\n                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same\n        \n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        nrow, ncol = len(grid), len(grid[0])\n        \n        def move(tup, d):\n            roffset, coffset = d\n            pr, pc, br, bc, dist = tup\n            pr += roffset\n            pc += coffset\n            illegal = (-1, -1, -1, -1, -1)\n            if pr < 0 or pr >= nrow or pc < 0 or pc >= ncol or grid[pr][pc] == \\\"#\\\":\n                return illegal\n            if pr == br and pc == bc:\n                br += roffset\n                bc += coffset\n                if br < 0 or br >= nrow or bc < 0 or bc >= ncol or grid[br][bc] == \\\"#\\\":\n                    return illegal\n                return (pr, pc, br, bc, dist+1)\n            if grid[pr][pc] == \\\".\\\":\n                return (pr, pc, br, bc, dist)\n        \n        p, t, b = [], [], []\n        for r in range(nrow):\n            for c in range(ncol):\n                if grid[r][c] == \\\"S\\\":\n                    p = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"T\\\":\n                    t = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"B\\\":\n                    b = (r, c)\n                    grid[r][c] = \\\".\\\"\n        \n        q = collections.deque()\n        q.append((p[0], p[1], b[0], b[1], 0))\n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        ret = float(\\\"inf\\\")\n        while q:\n            for _ in range(len(q)):\n                tup = q.popleft()\n                pr, pc, br, bc, dist = tup\n                if (br, bc) == t:\n                    ret = min(ret, dist)\n                if dist < visited[(pr, pc, br, bc)]:\n                    visited[(pr, pc, br, bc)] = dist\n                else:\n                    continue\n                for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n                    tup2 = move(tup, d)\n                    pr2, pc2, br2, bc2, dist2 = tup2\n                    if tup2[0] != -1 and dist2 < visited[(pr2, pc2, br2, bc2)]:\n                        q.append(tup2)\n                    \n        \n        return ret if ret < float(\\\"inf\\\") else -1", "class Solution:\n\n    def packString(self, box_row, box_col, player_row, player_col):\n        return str(box_row) + \\\",\\\" + str(box_col) + \\\",\\\" + str(player_row) + \\\",\\\" + str(player_col)\n\n    def unpackString(self, state):\n        return list(map(int, state.split(\\\",\\\")))\n\n    def posAvailable(self, grid, row, col):\n        if(row < 0 or row >= len(grid)):\n            return False\n        \n        if(col < 0 or col >= len(grid[0])):\n            return False\n        \n        if(grid[row][col] == \\\"#\\\"):\n            return False\n        \n        return True\n\n    def minPushBox(self, grid):\n        #Setup\n        box_row = -1\n        box_col = -1\n        player_row = -1\n        player_col = -1\n        target_row = -1\n        target_col = -1\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if(grid[i][j] == \\\"B\\\"):\n                    box_row = i\n                    box_col = j\n                elif(grid[i][j] == \\\"S\\\"):\n                    player_row = i\n                    player_col = j\n                elif(grid[i][j] == \\\"T\\\"):\n                    target_row = i\n                    target_col = j\n        memory = {}\n        distances = {}\n\n        moves = [ (0,1), (0, -1), (1, 0), (-1,0) ]\n        state = self.packString(box_row, box_col, player_row, player_col)\n        queue = [ [state] ]\n\n        distances[state] = 0\n        \n        dist = 0\n        while(dist < len(queue)):\n            while(queue[dist]):\n                state = queue[dist].pop(0)\n\n                if(state in memory):\n                    continue\n                memory[state] = 1\n\n                [box_row, box_col, player_row, player_col] = self.unpackString(state)\n\n                if(box_row == target_row and box_col == target_col):\n                    return dist\n\n                for move in moves :\n                    new_player_row = player_row + move[0]\n                    new_player_col = player_col + move[1]\n\n                    if not self.posAvailable(grid, new_player_row, new_player_col):\n                        continue\n\n                    if(new_player_row == box_row and new_player_col == box_col):\n                        L = 1\n                        new_box_row = box_row + move[0]\n                        new_box_col = box_col + move[1]\n                    else:\n                        L = 0\n                        new_box_row = box_row\n                        new_box_col = box_col\n                    \n                    if(not self.posAvailable(grid, new_box_row, new_box_col)):\n                        continue\n\n                    new_state = self.packString(new_box_row, new_box_col, new_player_row, new_player_col)\n\n                    curr_distance = distances[state] + L\n                    if(new_state not in distances or curr_distance < distances[new_state]):\n                        distances[new_state] = curr_distance\n                        while(len(queue) <= curr_distance):\n                            queue.append([])\n                        queue[curr_distance].append(new_state)\n            dist += 1\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        rows, cols = len(grid), len(grid[0])\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == \\\"T\\\":\n                    target = (r, c)\n                if grid[r][c] == \\\"B\\\":\n                    start_box = (r, c)\n                if grid[r][c] == \\\"S\\\":\n                    start_person = (r, c)\n                    \n        def heuristic(box):\n            # return abs(target[0] - box[0]) + abs(target[1] - box[1])\n            return 0;\n        \n        def out_bounds(location):  # return whether the location is in the grid and not a wall\n            r, c = location\n            if r < 0 or r >= rows:\n                return True\n            if c < 0 or c >= cols:\n                return True\n            return grid[r][c] == \\\"#\\\"\n                        \n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        visited = set()\n        \n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n            if (person, box) in visited: # do not visit same state again\n                continue\n            visited.add((person, box))\n            \n            for dr, dc in [[0, 1], [1, 0], [-1, 0], [0, -1]]:\n                new_person = (person[0] + dr, person[1] + dc)\n                if out_bounds(new_person):\n                    continue\n                    \n                if new_person == box:\n                    new_box = (box[0] + dr, box[1] + dc)\n                    if out_bounds(new_box):\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])\n                else:\n                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box]) # box remains same\n        \n        return -1", "from collections import deque \nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        def can_reach(x, y):\n            q = deque([x])\n            seen = set([x])\n            while q:\n                i, j = q.popleft()\n                if (i, j) == y:\n                    return True\n                for di, dj in (-1, 0), (1, 0), (0, 1), (0, -1):\n                    i_ = i + di\n                    j_ = j + dj\n                    if 0 <= i_ < m and 0 <= j_ < n and (i_, j_) not in seen and grid[i_][j_] == '.':\n                        seen.add((i_, j_))\n                        q.append((i_, j_))\n            return False\n            \n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'T':\n                    t = (i, j)\n                    grid[i][j] = '.'\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                    grid[i][j] = '.'\n                if grid[i][j] == 'S':\n                    s = (i, j)\n                    grid[i][j] = '.'\n        depth = 0\n        q = deque([(b, s)])\n        seen = set([(b, s)])\n        \n        while q:\n            depth += 1\n            for _ in range(len(q)):\n                b, s = q.popleft()\n                grid[b[0]][b[1]] = 'B'\n                for dx, dy in (-1, 0), (1, 0), (0, 1), (0, -1):\n                    x, y = b[0]+dx, b[1]+dy\n                    bx, by = b[0]-dx, b[1]-dy\n                    \n                    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:\n                        seen.add(((bx,by), b))\n                        q.append(((bx, by), b))\n                        if (bx, by) == t:\n                            return depth\n                grid[b[0]][b[1]] = '.'\n        return -1\n", "from time import time\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        d = dict()\n        \n        lim1 = len(grid)\n        lim2 = len(grid[0])\n        \n        for i in range(0,lim1):\n            for j in range(0,lim2):\n                if grid[i][j]!=\\\"#\\\":\n                    val = (i,j)\n                    d[val]=[]\n                    if i>0 and grid[i-1][j]!=\\\"#\\\":\n                        d[val].append((i-1,j))\n                    if j>0 and grid[i][j-1]!=\\\"#\\\":\n                        d[val].append((i,j-1))\n                    if i<lim1-1 and grid[i+1][j]!=\\\"#\\\":\n                        d[val].append((i+1,j))\n                    if j<lim2-1 and grid[i][j+1]!=\\\"#\\\":\n                        d[val].append((i,j+1))\n                        \n                    if grid[i][j]=='S':\n                        start = (i,j)\n                    elif grid[i][j]=='T':\n                        target = (i,j)\n                    elif grid[i][j]=='B':\n                        box = (i,j)\n        mx = max(lim1,lim2)\n        def gotobox(c1,c2,b):\n            arr = [[-1 for i in range(0,mx)] for j in range(0,mx)]\n            arr[c1[0]][c1[1]]=1\n            f = []\n            begin = [c1]\n            while 1!=-1:\n                cache = []\n                ###print(f)\n                for x in begin:\n                    if x in c2 and x not in f:\n                        \n                        f.append(x)\n                        \n                        \n                    for y in d[x]:\n                        \n                        ###if y==(2,2):print(1)\n                        if y!=b and arr[y[0]][y[1]]==-1:\n                            arr[y[0]][y[1]]=1\n                            cache.append(y)\n                ###print(cache,c2)\n                if cache==[]:\n                    \n                    return f\n                \n                begin = cache\n        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)]    \n        \n        tmp1 = [[start,box,0]]\n        while 1!=-1:\n            \n            tmp2 = []\n            \n            for x in tmp1:\n                \n                if arr2[x[0][0]][x[0][1]][x[1][0]][x[1][1]]==-1:\n                    arr2[x[0][0]][x[0][1]][x[1][0]][x[1][1]]=1\n                    for y in d[x[0]]:\n\n                        if x[1]==target:\n\n                            return x[-1]\n                        else:\n                            vals = gotobox(x[0],d[x[1]],x[1])\n\n                            if vals ==-1:return -1\n\n                            for z in vals:\n                                for a in d[x[1]]:\n\n                                    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])\n                    \n                        \n            if tmp2==[]:return -1\n            tmp1 = tmp2\n     \n                                \n                        \n                        \n            ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        def move(node, dx, dy):\n            px, py, bx, by, dist = node\n            px += dx\n            py += dy\n\n            if px < 0 or px >= m or py < 0 or py >= n or grid[px][py] == \\\"#\\\":\n                return (-1, -1, -1, -1, -1)\n            if px == bx and py == by:\n                bx += dx\n                by += dy\n                if bx < 0 or bx >= m or by < 0 or by >= n or grid[bx][by] == \\\"#\\\":\n                    return (-1, -1, -1, -1, -1)                \n                return (px, py, bx, by, dist+1)\n            if grid[px][py] == \\\".\\\":\n                return (px, py, bx, by, dist)\n        \n        player, target, box = [], [], []\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"S\\\":\n                    player = (i, j)\n                    grid[i][j] = \\\".\\\"\n                if grid[i][j] == \\\"T\\\":\n                    target = (i, j)\n                    grid[i][j] = \\\".\\\"\n                if grid[i][j] == \\\"B\\\":\n                    box = (i, j)\n                    grid[i][j] = \\\".\\\"\n        \n        queue = collections.deque()\n        queue.append((player[0], player[1], box[0], box[1], 0))\n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n        res = float(\\\"inf\\\")\n        \n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                node = queue.popleft()\n                px, py, bx, by, dist = node\n                if (bx, by) == target:\n                    res = min(res, dist)\n                if dist < visited[(px, py, bx, by)]:\n                    visited[(px, py, bx, by)] = dist\n                else:\n                    continue\n                for dx, dy in directions:\n                    newNode = move(node, dx, dy)\n                    px2, py2, bx2, by2, dist2 = newNode\n                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:\n                        queue.append(newNode)\n                    \n        \n        return res if res < float(\\\"inf\\\") else -1\n    \n    \n    \n    \n    \n    \n        \n        \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        def move(tup, d):\n            roffset, coffset = d\n            pr, pc, br, bc, dist = tup\n            pr += roffset\n            pc += coffset\n            illegal = (-1, -1, -1, -1, -1)\n            if pr < 0 or pr >= m or pc < 0 or pc >= n or grid[pr][pc] == \\\"#\\\":\n                return illegal\n            if pr == br and pc == bc:\n                br += roffset\n                bc += coffset\n                if br < 0 or br >= m or bc < 0 or bc >= n or grid[br][bc] == \\\"#\\\":\n                    return illegal\n                return (pr, pc, br, bc, dist+1)\n            if grid[pr][pc] == \\\".\\\":\n                return (pr, pc, br, bc, dist)\n        \n        player, t, b = [], [], []\n        for r in range(m):\n            for c in range(n):\n                if grid[r][c] == \\\"S\\\":\n                    player = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"T\\\":\n                    target = (r, c)\n                    grid[r][c] = \\\".\\\"\n                if grid[r][c] == \\\"B\\\":\n                    box = (r, c)\n                    grid[r][c] = \\\".\\\"\n        \n        queue = collections.deque()\n        queue.append((player[0], player[1], box[0], box[1], 0))\n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        res = float(\\\"inf\\\")\n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                node = queue.popleft()\n                px, py, bx, by, dist = node\n                if (bx, by) == target:\n                    res = min(res, dist)\n                if dist < visited[(px, py, bx, by)]:\n                    visited[(px, py, bx, by,)] = dist\n                else:\n                    continue\n                for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n                    newNode = move(node, d)\n                    px2, py2, bx2, by2, dist2 = newNode\n                    if newNode[0] != -1 and dist2 < visited[(px2, py2, bx2, by2)]:\n                        queue.append(newNode)\n                    \n        \n        return res if res < float(\\\"inf\\\") else -1\n    \n    \n    \n    \n    \n    \n        \n        \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m,n=len(grid),len(grid[0])\n        dirs=[(0,1),(0,-1),(1,0),(-1,0)]\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]=='S':\n                    S=(i,j)\n                if grid[i][j]=='B':\n                    B=(i,j)\n                if grid[i][j]=='T':\n                    T=(i,j)\n                    \n                    \n        def check(x,y):    #\u5224\u65ad\u8fd9\u4e2a\u4f4d\u7f6e\u662f\u5426\u6709\u6548\n            return 0<=x<m and 0<=y<n and grid[x][y]!='#'\n                    \n            \n        def canmoveto(e,b,q,visit):          #\u5224\u65ad\u4eba\u80fd\u5426\u5230\u8fbe\u76ee\u6807\u4f4d\u7f6e\n            while q:\n                p=q.pop(0)\n                if p==e:\n                    return True\n                for dx,dy in dirs:\n                    nx,ny=p[0]+dx,p[1]+dy\n                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:\n                        q.append((nx,ny))\n                        visit.add((nx,ny))\n            return False\n        \n        def move(e,q,visit):   #\u5224\u65ad\u4eba\u80fd\u5426\u628a\u7bb1\u5b50\u63a8\u5230\u76ee\u6807\u4f4d\u7f6e\n            res = 0\n            while q:\n                for _ in range(len(q)):\n                    b, p = q.pop(0)\n                    if b == e:\n                        return res\n                    \n                    for i, j in dirs:\n                        nx, ny = b[0] + i, b[1] + j #\n                        if check(nx, ny) and \\\\\n                            check(b[0] - i, b[1] - j) and\\\\\n                            ((nx, ny), b) not in visit and \\\\\n                            canmoveto((b[0] - i, b[1] - j), b, [p], set([p])):\n                            q.append(((nx, ny), b))\n                            visit.add(((nx, ny), b))\n                res += 1\n            return -1\n        return move(T,[(B,S)],set([(B,S)]))\n                        \n                \n                \n        \n        ", "class Solution:\n    def minPushBox(self, grid) -> int:\n        from collections import deque\n        r, c = len(grid), len(grid[0])\n        di = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n\n        def bfs(sx, sy, ex, ey, path):\n            t = deque()\n            s = set()\n            s.add(str((sx, sy)))\n            t.append([sx, sy])\n            while t:\n                x, y = t.popleft()\n                if x == ex and y == ey:\n                    return True\n                for i, j in di:\n                    ti = x + i\n                    tj = y + j\n                    if (0 <= ti < r and 0 <= tj < c \n                        and path[ti][tj] == '.'\n                        and str((ti, tj)) not in s):\n                        s.add(str((ti, tj)))\n                        t.append([ti, tj])\n            return False\n\n        bx = by = sx = sy = tx = ty = -1\n        for i in range(r):\n            for j in range(c):\n                if grid[i][j] == 'B':\n                    bx, by = i, j\n                    grid[i][j] = '.'\n                if grid[i][j] == 'S':\n                    sx, sy = i, j\n                    grid[i][j] = '.'\n                if grid[i][j] == 'T':\n                    tx, ty = i, j\n                    grid[i][j] = '.'\n\n        if -1 in [bx, by, sx, sy, tx, ty]:\n            return -1\n\n        t = deque()\n        s = set()\n        t.append([bx, by, sx, sy, 0])\n        s.add(str((bx, by, sx, sy)))\n\n        while t:\n            bx, by, sx, sy, step = t.popleft()\n            if bx == tx and by == ty:\n                return step\n            grid[bx][by] = 'B'\n            for i, j in di:\n                ti = bx + i\n                tj = by + j\n                tii = bx - i\n                tjj = by - j\n                if (0 <= ti < r and 0 <= tj < c and grid[ti][tj] == '.'\n                    and str((ti, tj, bx, by)) not in s and 0 <= tii < r\n                    and 0 <= tjj < c and grid[tii][tjj] == '.' \n                    and bfs(sx, sy, tii, tjj, grid)):\n                    t.append([ti, tj, bx, by, step + 1])\n                    s.add(str((ti, tj, bx, by)))\n\n            grid[bx][by] = '.'\n\n        return -1\n", "from heapq import *\nclass Solution:\n    MOVES = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"S\\\": playerPos = (i, j)\n                if grid[i][j] == \\\"B\\\": boxPos = (i, j)\n                if grid[i][j] == \\\"T\\\": targetPos = (i, j)\n        \n        steps = [[999999] * n for _ in range(m)]     # \u8bb0\u5f55\u4ecesource/boxPos\u5230(i, j)\u7684\u6b65\u6570\uff0c\u8fd9\u4e2aextra space\u5728A*\u662f\u5fc5\u987b\u7684\uff0c\u7528\u7a7a\u95f4\u6362\u65f6\u95f4\n        steps[boxPos[0]][boxPos[1]] = 0\n        \n        hq = []\n        visited = set()     # \u5176\u5b9eA*\u7b97\u6cd5\u91cc\u9762\u4e5f\u53ef\u4ee5\u4e0d\u7528\u52a0visited, \u56e0\u4e3a\u6bcf\u6b21\u90fd\u662f\u671d\u66fc\u54c8\u987f\u6700\u5c0f\u7684\u65b9\u5411\u8d70\u7684\uff0c\u5f88\u5c11\u4f1a\u91cd\u590d\u8bbf\u95ee\u540c\u4e00\u4e2a\u8282\u70b9\uff0c\u4e0d\u50cfbfs\u4f1a\u7ecf\u5e38\u8bbf\u95ee\u5230\u540c\u4e00\u4e2a\u8282\u70b9\n        heappush(hq, (abs(boxPos[0]-targetPos[0]) + abs(boxPos[1]-targetPos[1]), 0, boxPos, playerPos)) \n        while hq:\n            hueristicEstimation, step, currBoxPos, currPlayerPos = heappop(hq)\n            if currBoxPos == targetPos:\n                return steps[currBoxPos[0]][currBoxPos[1]]\n\n            for move in self.MOVES:\n                nextBoxPos_x, nextBoxPos_y = currBoxPos[0] + move[0], currBoxPos[1] + move[1]\n                oppositeNextBoxPos_x, oppositeNextBoxPos_y = currBoxPos[0] - move[0], currBoxPos[1] - move[1]\n                nextBoxPos = (nextBoxPos_x, nextBoxPos_y)\n                oppositeNextBoxPos = (oppositeNextBoxPos_x, oppositeNextBoxPos_y)\n                if nextBoxPos_x < 0 or nextBoxPos_x >= m or nextBoxPos_y < 0 or nextBoxPos_y >= n:\n                    continue\n                if grid[nextBoxPos_x][nextBoxPos_y] == \\\"#\\\":\n                    continue\n                if (nextBoxPos, currBoxPos) in visited:\n                    continue\n                if not self.playerCanReach(grid, currPlayerPos, oppositeNextBoxPos, currBoxPos):\n                    continue\n                heappush(hq, (step + abs(nextBoxPos[0]-targetPos[0]) + abs(nextBoxPos[1]-targetPos[1]), step + 1, nextBoxPos, currBoxPos)) \n                visited.add((nextBoxPos, currBoxPos))    # visited\u91cc\u9762\u5e94\u8be5\u88c5\u5165(boxPos, the pos where the boxPos comes from)\n                steps[nextBoxPos[0]][nextBoxPos[1]] = step + 1\n                    \n        return -1\n                    \n    def playerCanReach(self, grid, startPos, endPos, boxPos):\n        \\\"\\\"\\\"\n        use manhatan distance as Heuristic esitimation for A-star algorithm: steps + (abs(nextPos[0]-endPos[0]) + abs(nextPos[1]-endPos[1])).  \n        put the heuristic estimation in the hq, together with steps, so the hq stores \n        (heristic estimation of the minimum steps needed from source to target, steps, nextPos). \n        \\\"\\\"\\\"\n        m, n = len(grid), len(grid[0])\n        steps = [[999999] * n for _ in range(m)]     # \u8bb0\u5f55\u4ecesource/boxPos\u5230(i, j)\u7684\u6b65\u6570\uff0c\u8fd9\u4e2aextra space\u5728A*\u662f\u5fc5\u987b\u7684\uff0c\u7528\u7a7a\u95f4\u6362\u65f6\u95f4\n        steps[startPos[0]][startPos[1]] = 0\n        hq = []\n        visited = set()\n        heappush(hq, (abs(startPos[0] - endPos[0]) + abs(startPos[1] - endPos[1]), 0, startPos))\n        visited.add(startPos)\n        while hq:\n            hueristicEstimation, step, currPos = heappop(hq)\n            if currPos == endPos:\n                return True\n            for move in self.MOVES:\n                nextPos_x, nextPos_y = currPos[0] + move[0], currPos[1] + move[1]\n                nextPos = (nextPos_x, nextPos_y)\n                if nextPos_x < 0 or nextPos_x >= m or nextPos_y < 0 or nextPos_y >= n:\n                    continue\n                if grid[nextPos_x][nextPos_y] == \\\"#\\\" or nextPos == boxPos:      # \u6613\u9519\u70b92: \u9047\u5230box\u7684\u8bdd\u4e5f\u4e0d\u80fd\u524d\u8fdb\n                    continue\n                if nextPos in visited:\n                    continue\n                heappush(hq, (step + abs(nextPos[0] - endPos[0]) + abs(nextPos[1] - endPos[1]), step + 1, nextPos))\n                visited.add(nextPos)\n                \n        return False", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i, j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i, j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i, j)\n                    \n        def valid(x, y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] != \\\"#\\\"\n        \n        def check(curr, dest, box):\n            queue = deque([curr])\n            v = set()\n            while queue:\n                pos = queue.popleft()\n                if pos == dest:\n                    return True\n                new_pos = [(1,0),(-1,0),(0,1),(0,-1)]\n                for x, y in new_pos:\n                    nx, ny = pos[0]+x, pos[1]+y\n                    if valid(nx, ny) and (nx, ny) not in v and (nx, ny) != box:\n                        v.add((nx, ny))\n                        queue.append((nx, ny))\n                        \n            return False\n        \n        \n        \n        queue = deque([(0,box,person)])\n        visited = {box+person}\n        while queue:\n            dist, box, person = queue.popleft()\n            if box == target:\n                return dist\n            \n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            # b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            b_coord = [(1,0),(-1,0),(0,1),(0,-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n            \n            for new_box,new_person in zip(b_coord,p_coord):\n                bx, by = box[0]+new_box[0], box[1]+new_box[1]\n                if valid(bx, by) and box+new_box not in visited:\n                    if valid(*new_person) and check(person,new_person,box):\n                        visited.add((box+new_box))\n                        queue.append((dist+1,(bx, by),box))\n                        ###after shifting, the person's pos is old box's pos\n        return -1\n            \n        \n                    \n                \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n        \n        \n        def check(p1, p2, t1, t2, b1, b2):#g is new grid\n            visited = visited = [[False for _ in range(n)] for _ in range(m)]\n            queue = collections.deque()\n            queue.append((p1, p2))\n            visited[p1][p2] = True\n            \n            while queue:\n                x, y = queue.popleft()\n                if (x, y) == (t1, t2):\n                    return True\n                for dx, dy in moves:\n                    nx, ny = x + dx, y + dy\n                    if 0 <= nx < m  and 0 <= ny < n:\n                        if visited[nx][ny]: continue\n                        if (nx, ny) == (t1, t2): return True\n                        if (nx, ny) != (b1, b2) and grid[nx][ny] != '#':\n                            queue.append((nx, ny))\n                            visited[nx][ny] = True\n            return False\n        \n        def inbound(x, y):\n            return 0 <= x < m and 0 <= y < n\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] != '#':\n                    if grid[i][j] == 'S':\n                        player = (i, j)\n                    elif grid[i][j] == 'B':\n                        box = (i, j)\n                    elif grid[i][j] == 'T':\n                        end = (i, j)\n        #player box end\n        p1, p2 = player\n        b1, b2 = box\n        e1, e1 = end    \n        \n        visited = set()\n        step = -1\n        \n        queue = collections.deque()\n        queue.append((b1, b2, p1, p2))\n        \n        while queue:\n            step += 1\n            for _ in range(len(queue)):#\u522b\u5fd8\u4e86\u662f\u5c42\u5e8f\u904d\u5386\uff01\uff01\uff01\n                x, y, p1, p2 = queue.popleft()\n                #up\n                if inbound(x - 1, y) and inbound(x + 1, y) and grid[x + 1][y] != '#' and check(p1, p2, x + 1, y, x, y):\n                    if (x - 1, y, x, y) not in visited:\n                        if grid[x - 1][y] != '#':\n                            if grid[x - 1][y] == 'T':\n                                return step + 1\n                            else:\n                                queue.append((x - 1, y, x, y))\n                                visited.add((x - 1, y, x, y))\n                                visited.add((x, y, x + 1, y))\n                #down\n                if inbound(x - 1, y) and inbound(x + 1, y) and grid[x - 1][y] != '#' and check(p1, p2, x - 1, y, x, y):\n                    if (x + 1, y, x, y) not in visited:\n                        if grid[x + 1][y] != '#':\n                            if grid[x + 1][y] == 'T':\n                                return step + 1\n                            else:\n                                queue.append((x + 1, y, x, y))\n                                visited.add((x + 1, y, x, y))\n                                visited.add((x, y, x - 1, y))\n\n                #left\n                if inbound(x, y + 1) and inbound(x, y - 1) and grid[x][y + 1] != '#' and check(p1, p2, x, y + 1, x, y):\n                    if (x, y - 1, x, y) not in visited:\n                        if grid[x][y - 1] != '#':\n                            if grid[x][y - 1] == 'T':\n                                return step + 1\n                            else:\n                                queue.append((x, y - 1, x, y))\n                                visited.add((x, y - 1, x, y))\n                                visited.add((x, y, x, y + 1))\n\n                #right\n                if inbound(x, y + 1) and inbound(x, y - 1) and grid[x][y - 1] != '#' and check(p1, p2, x, y - 1, x, y):\n                    if (x, y + 1, x, y) not in visited:\n                        if grid[x][y + 1] != '#':\n                            if grid[x][y + 1] == 'T':\n                                return step + 1\n                            else:\n                                queue.append((x, y + 1, x, y))\n                                visited.add((x, y + 1, x, y))\n                                visited.add((x, y, x, y - 1))\n        \n        return -1", "'''\nLets break the question into simple parts:\n\nLets think that we have no person and we have to find the minimum path between box and the target. Easy right? Simple BFS.\n\nIf you know how to solve the first part, what I actually do is modified first part with few constraints.\n\nI just check whether the box can be shifted to the new position(up, down, left, right)\nFor it to be shifted to the new position the person has to be in a corresponding position right?\nSo we check if the person can travel from his old position to his corresponding new position(using another BFS).\nIf the person can travel to his new position than the box can be shifted, otherwise the box cannot be shifted.\nWe keep repeating step 2 until we reach the target or it is not possible to move the box anymore.\n\nNOTE : 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.\n'''\n\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n\n        # this loop is to get the coordinates of target, box and person. Nothing else is gained here\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i,j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i,j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i,j)\n\n        # this function checks whether the given coordinates/indices are valid to go\n        def valid(x,y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'\n\n        # this function checks whether the person can travel from current postition to destination position.\n        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.\n        def check(curr,dest,box):\n            que = deque([curr])\n            v = set()\n            while que:\n                pos = que.popleft()\n                if pos == dest: return True\n                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]\n                for x,y in new_pos:\n                    if valid(x,y) and (x,y) not in v and (x,y)!=box:\n                        v.add((x,y))\n                        que.append((x,y))\n            return False\n\n        q = deque([(0,box,person)])\n        vis = {box+person}\n        # this is the main bfs which gives us the answer\n        while q :\n            dist, box, person = q.popleft()\n            if box == target: # return the distance if box is at the target\n                return dist\n\n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n\n            for new_box,new_person in zip(b_coord,p_coord): \n                # we check if the new box coordinates are valid and our current state is not in vis\n                if valid(*new_box) and new_box+box not in vis:\n                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates\n                    if valid(*new_person) and check(person,new_person,box):\n                        vis.add(new_box+box)\n                        q.append((dist+1,new_box,box))\n\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n         # this loop is to get the coordinates of target, box and person. Nothing else is gained here\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i,j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i,j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i,j)\n\n        # this function checks whether the given coordinates/indices are valid to go\n        def valid(x,y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'\n\n        # this function checks whether the person can travel from current postition to destination position.\n        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.\n        def check(curr,dest,box):\n            que = deque([curr])\n            v = set()\n            while que:\n                pos = que.popleft()\n                if pos == dest: return True\n                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]\n                for x,y in new_pos:\n                    if valid(x,y) and (x,y) not in v and (x,y)!=box:\n                        v.add((x,y))\n                        que.append((x,y))\n            return False\n\n        q = deque([(0,box,person)])\n        vis = {box+person}\n        # this is the main bfs which gives us the answer\n        while q :\n            dist, box, person = q.popleft()\n            if box == target: # return the distance if box is at the target\n                return dist\n\n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n\n            for new_box,new_person in zip(b_coord,p_coord): \n                # we check if the new box coordinates are valid and our current state is not in vis\n                if valid(*new_box) and new_box+box not in vis:\n                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates\n                    if valid(*new_person) and check(person,new_person,box):\n                        vis.add(new_box+box)\n                        q.append((dist+1,new_box,box))\n\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dirs = [(0, 1), (-1, 0), (1, 0), (0, -1)]\n        m, n = len(grid), len(grid[0])\n        def connected(s, e):\n            q = collections.deque([s])\n            visited = set([s])\n            while q:\n                r, c = q.popleft()\n                if (r, c) == e: return True\n                for dr, dc in dirs:\n                    nr, nc = r+dr, c+dc\n                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '.':\n                        if (nr, nc) not in visited:\n                            visited.add((nr, nc))\n                            q.append((nr, nc))\n            return False\n        \n        B = S = T = (0, 0)\n        for r in range(m):\n            for c in range(n):\n                if grid[r][c] == 'B': \n                    B = (r, c)\n                    grid[r][c] = '.'\n                elif grid[r][c] == 'S': \n                    S = (r, c)\n                    grid[r][c] = '.'\n                elif grid[r][c] == 'T': \n                    T = (r, c)\n                    grid[r][c] = '.'\n                    \n        ans = 0\n        q = collections.deque([(B, S, 0)])\n        visited = set([(B, S)])\n        while q:\n            (r, c), (rs, cs), step = q.popleft()\n            if (r, c) == T: return step\n            for dr, dc in dirs:\n                nr, nc = r+dr, c+dc\n                pr, pc = r-dr, c-dc\n                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '.' and ((nr, nc), (r, c)) not in visited:\n                    grid[r][c] = 'B'\n                    if 0 <= pr < m and 0 <= pc < n and grid[pr][pc] == '.' and connected((pr, pc), (rs, cs)):\n                        visited.add(((nr, nc), (r, c)))\n                        q.append(((nr, nc), (r, c), step+1))\n                    grid[r][c] = '.'\n        return -1\n                        \n            \n                    \n            \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i, j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i, j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i, j)\n                    \n        def valid(x, y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] != \\\"#\\\"\n        \n        def check(curr, dest, box):\n            queue = deque([curr])\n            v = set()\n            while queue:\n                pos = queue.popleft()\n                if pos == dest:\n                    return True\n                new_pos = [(1,0),(-1,0),(0,1),(0,-1)]\n                for x, y in new_pos:\n                    nx, ny = pos[0]+x, pos[1]+y\n                    if valid(nx, ny) and (nx, ny) not in v and (nx, ny) != box:\n                        v.add((nx, ny))\n                        queue.append((nx, ny))\n                        \n            return False\n        \n        \n        \n        queue = deque([(0,box,person)])\n        visited = {box+person}\n        while queue:\n            dist, box, person = queue.popleft()\n            if box == target:\n                return dist\n            \n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            # b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            b_coord = [(1,0),(-1,0),(0,1),(0,-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            # p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n            p_coord = [(-1,0),(1,0),(0,-1),(0,1)]\n            \n            for new_box,new_person in zip(b_coord,p_coord):\n                bx, by = box[0]+new_box[0], box[1]+new_box[1]\n                px, py = box[0]+new_person[0], box[1]+new_person[1]\n                \n                if valid(bx, by) and box+new_box not in visited:\n                    if valid(px, py) and check(person,(px, py),box):\n                        visited.add((box+new_box))\n                        queue.append((dist+1,(bx, by),box))\n                        ###after shifting, the person's pos is old box's pos\n        return -1\n            \n        \n                    \n                \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        def is_floor(i, j):\n            return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] != '#'\n        def bfs(start_i, start_j, box_i, box_j):\n            visited, queue, reach_list = [[0 for _ in range(n)] for _ in range(m)], [(start_i, start_j)], []\n            visited[start_i][start_j] = 1\n            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)])\n            while queue:\n                start_i, start_j = queue.pop(0)\n                for delta_i, delta_j in [(0, -1), (-1, 0), (0, 1), (1, 0)]:\n                    if start_i + delta_i == box_i and start_j + delta_j == box_j:\n                        reach_list.append((delta_i, delta_j))\n                        if len(reach_list) >= reach_list_upbound:\n                            return reach_list\n                    elif is_floor(start_i + delta_i, start_j + delta_j) and visited[start_i + delta_i][start_j + delta_j] == 0:\n                        visited[start_i + delta_i][start_j + delta_j] = 1\n                        queue.append((start_i + delta_i, start_j + delta_j))\n            return reach_list\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'S': source = (i, j)\n                elif grid[i][j] == 'B': box = (i, j)\n                elif grid[i][j] == 'T': target = (i, j)\n        queue = [(source, box, 0)]\n        visited = set()\n        while queue:\n            source, box, depth = queue.pop(0)\n            if box[0] == target[0] and box[1] == target[1]: return depth\n            reach_list = bfs(source[0], source[1], box[0], box[1])\n            for mov in reach_list:\n                s, b = (box[0], box[1]), (box[0] + mov[0], box[1] + mov[1])\n                if is_floor(b[0], b[1]) and (s, b) not in visited:\n                    visited.add((s, b))\n                    queue.append((s, b, depth + 1))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        n = len(grid)\n        m = len(grid[0])\n        walls = set()\n        for i in range(-1, n+1):\n            for j in [-1,m]:\n                walls.add(i + j *1j)\n        for i in [-1,n]:\n            for j in range(-1, m+1):\n                walls.add(i + j *1j)\n\n        for i, row in enumerate(grid):\n            for j, c in enumerate(row):\n                if c == \\\"S\\\":\n                    spos = i + j * 1j\n                elif c == \\\"T\\\":\n                    tpos = i + j * 1j\n                elif c == \\\"B\\\":\n                    bpos = i + j * 1j\n                elif c == \\\"#\\\":\n                    walls.add(i + j * 1j)\n        \n        def children(node):\n            return [node + x for x in [1,-1,1j,-1j]]\n        \n        def connected(pos1, pos2, bpos):\n            q = [pos1]\n            seen = set(q)\n            while q:\n                node = q.pop(0)\n                if node == pos2: return True\n                for child in children(node):\n                    if child in walls or child == bpos: continue\n                    if child in seen: continue\n                    seen.add(child)\n                    q.append(child)\n            return False\n        \n        depth = {(spos, bpos): 0}\n        \n        q = [(spos, bpos)]\n        while q:\n            spos, bpos = q.pop(0)\n            if bpos == tpos:\n                return depth[(spos, bpos)]\n            for child in children(bpos):\n                if child in walls: continue\n                newspos = 2*bpos - child\n                if newspos in walls: continue\n                if not connected(spos, newspos, bpos): continue\n                if (newspos, child) in depth: continue\n                depth[(newspos, child)] = depth[(spos, bpos)] + 1\n                q.append((newspos, child))\n        return -1\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m,n=len(grid),len(grid[0])\n        dirs=[(0,1),(0,-1),(1,0),(-1,0)]\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]=='S':\n                    S=(i,j)\n                if grid[i][j]=='B':\n                    B=(i,j)\n                if grid[i][j]=='T':\n                    T=(i,j)\n                    \n                    \n        def check(x,y):    #\u5224\u65ad\u8fd9\u4e2a\u4f4d\u7f6e\u662f\u5426\u6709\u6548\n            return 0<=x<m and 0<=y<n and grid[x][y]!='#'\n                    \n            \n        def canmoveto(e,b,q,visit):          #\u5224\u65ad\u4eba\u80fd\u5426\u5230\u8fbe\u76ee\u6807\u4f4d\u7f6e\n            while q:\n                p=q.pop(0)\n                if p==e:\n                    return True\n                for dx,dy in dirs:\n                    nx,ny=p[0]+dx,p[1]+dy\n                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:\n                        q.append((nx,ny))\n                        visit.add((nx,ny))\n            return False\n        \n        def move(e,q,visit):   #\u5224\u65ad\u4eba\u80fd\u5426\u628a\u7bb1\u5b50\u63a8\u5230\u76ee\u6807\u4f4d\u7f6e\n            res = 0\n            while q:\n                size=len(q)\n                for _ in range(size):\n                    b, p = q.pop(0)\n                    if b == e:\n                        return res\n                    \n                    for i, j in dirs:\n                        nx, ny = b[0] + i, b[1] + j #\n                        if check(nx, ny) and \\\\\n                            check(b[0] - i, b[1] - j) and\\\\\n                            ((nx, ny), b) not in visit and \\\\\n                            canmoveto((b[0] - i, b[1] - j), b, [p], set([p])):\n                            q.append(((nx, ny), b))\n                            visit.add(((nx, ny), b))\n                res += 1\n            return -1\n        return move(T,[(B,S)],set([(B,S)]))\n                        \n                \n                \n        \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        # where can player move next?\n        def player_moves(box_i, box_j, p_i, p_j):\n            res=[]\n            if p_i > 0 and grid[p_i-1][p_j] != '#' and (p_i-1, p_j) != (box_i, box_j):\n                res.append((p_i-1, p_j))\n            if p_i < len(grid)-1 and grid[p_i+1][p_j] != '#' and (p_i+1, p_j) != (box_i, box_j):\n                res.append((p_i+1, p_j))\n            if p_j > 0 and grid[p_i][p_j-1] != '#' and (p_i, p_j-1) != (box_i, box_j):\n                res.append((p_i, p_j-1))    \n            if p_j < len(grid[0])-1 and grid[p_i][p_j+1] != '#' and (p_i, p_j+1) != (box_i, box_j):\n                res.append((p_i, p_j+1))\n            return res\n\n        # Can player walk to this cell?            \n        def is_accessible(cell_i, cell_j, box_i, box_j, p_i, p_j):\n            if grid[cell_i][cell_j]=='#':\n                return False\n            q=deque()\n            visited=set()\n            q.append((p_i, p_j))\n            visited.add((p_i, p_j))\n            while q:\n                size=len(q)\n                for i in range(size):\n                    pop=q.popleft()\n                    if pop==(cell_i,cell_j):\n                        return True\n                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):\n                        if nex not in visited:\n                            q.append(nex)\n                            visited.add(nex)\n            return False \n            \n        # each state is defined by box location and player location\n        def box_moves(state):\n            res=set()\n            box_i, box_j, p_i, p_j = state[0], state[1], state[2], state[3]\n            # 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\n            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\n                res.add((box_i+1, box_j, box_i, box_j))\n            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\n                res.add((box_i-1, box_j, box_i, box_j))\n            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\n                res.add((box_i, box_j+1, box_i, box_j))\n            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\n                res.add((box_i, box_j-1, box_i, box_j))\n            return res\n            \n        def start_state():\n            box_i, box_j, p_i, p_j = -1, -1, -1, -1\n            for i in range(len(grid)):\n                for j in range(len(grid[0])):\n                    if grid[i][j]=='B':\n                        box_i, box_j = i, j\n                    elif grid[i][j]=='S':\n                        p_i, p_j = i, j\n            return (box_i, box_j, p_i, p_j)\n                \n        q=deque()\n        visited=set()\n        start=start_state()\n        q.append(start)\n        visited.add(start)\n        moves=-1\n        while q:\n            size=len(q)\n            moves +=1\n            for i in range(size):\n                pop=q.popleft()\n                if grid[pop[0]][pop[1]]=='T':\n                    return moves\n                for nx in box_moves(pop):                    \n                    if nx not in visited:\n                        q.append(nx)\n                        visited.add(nx)\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n        R, C = len(grid), len(grid[0])\n        b_pos = s_pos = t_pos = None\n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 'B':\n                    b_pos = (r, c)\n                if grid[r][c] == 'S':\n                    s_pos = (r, c)\n                if grid[r][c] == 'T':\n                    t_pos = (r, c)\n        def is_empty(r, c):\n            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'\n        @lru_cache(None)\n        def can_reach(r1, c1, r2, c2, br, bc):\n            if not is_empty(r2, c2):\n                return False\n            q = [(r1, c1)]\n            used = set()\n            for r, c in q:\n                if (r, c) in used or (r, c) == (br, bc):\n                    continue\n                used.add((r, c))\n                if (r, c) == (r2, c2):\n                    return True\n                for dr, dc in dirs:\n                    nr, nc = dr + r, dc + c\n                    if is_empty(nr, nc):\n                        q.append((nr, nc))\n            return False\n        #print(f\\\"b_pos {b_pos}, t_pos {t_pos}\\\")\n        visited = set()\n        pq = [(0, b_pos, s_pos)]\n        while pq:\n            #print(f\\\"pq {pq}\\\")\n            steps, b_pos, s_pos = heappop(pq)\n            if (b_pos, s_pos) in visited:\n                continue\n            visited.add((b_pos, s_pos))\n            if b_pos == t_pos:\n                return steps\n            sr, sc = s_pos\n            br, bc = b_pos\n            for dr, dc in dirs:\n                br1, bc1 = br + dr, bc + dc\n                br2, bc2 = br - dr, bc - dc\n                #print(f\\\"(br1, bc1) {br1, bc1}, (br2, bc2) {br2, bc2}\\\")\n                if is_empty(br2, bc2) and can_reach(sr, sc, br1, bc1, br, bc):\n                    heappush(pq, (steps + 1, (br2, bc2), b_pos))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n        R, C = len(grid), len(grid[0])\n        b_pos = s_pos = t_pos = None\n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 'B':\n                    b_pos = (r, c)\n                if grid[r][c] == 'S':\n                    s_pos = (r, c)\n                if grid[r][c] == 'T':\n                    t_pos = (r, c)\n        def is_empty(r, c):\n            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'\n\n        def can_reach(r1, c1, r2, c2, br, bc):\n            if not is_empty(r2, c2):\n                return False\n            q = [(r1, c1)]\n            used = set()\n            for r, c in q:\n                if (r, c) in used or (r, c) == (br, bc):\n                    continue\n                used.add((r, c))\n                if (r, c) == (r2, c2):\n                    return True\n                for dr, dc in dirs:\n                    nr, nc = dr + r, dc + c\n                    if is_empty(nr, nc):\n                        q.append((nr, nc))\n            return False\n        #print(f\\\"b_pos {b_pos}, t_pos {t_pos}\\\")\n        visited = set()\n        pq = [(0, b_pos, s_pos)]\n        while pq:\n            #print(f\\\"pq {pq}\\\")\n            steps, b_pos, s_pos = heappop(pq)\n            if (b_pos, s_pos) in visited:\n                continue\n            visited.add((b_pos, s_pos))\n            if b_pos == t_pos:\n                return steps\n            sr, sc = s_pos\n            br, bc = b_pos\n            for dr, dc in dirs:\n                br1, bc1 = br + dr, bc + dc\n                br2, bc2 = br - dr, bc - dc\n                #print(f\\\"(br1, bc1) {br1, bc1}, (br2, bc2) {br2, bc2}\\\")\n                if is_empty(br2, bc2) and can_reach(sr, sc, br1, bc1, br, bc):\n                    heappush(pq, (steps + 1, (br2, bc2), b_pos))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        def player_moves(box_i, box_j, player_i, player_j):\n            res=[]\n            if player_i > 0 and grid[player_i-1][player_j] != '#' and (player_i-1, player_j) != (box_i, box_j):\n                res.append((player_i-1, player_j))\n            if player_i < len(grid)-1 and grid[player_i+1][player_j] != '#' and (player_i+1, player_j) != (box_i, box_j):\n                res.append((player_i+1, player_j))\n            if player_j > 0 and grid[player_i][player_j-1] != '#' and (player_i, player_j-1) != (box_i, box_j):\n                res.append((player_i, player_j-1))    \n            if player_j < len(grid[0])-1 and grid[player_i][player_j+1] != '#' and (player_i, player_j+1) != (box_i, box_j):\n                res.append((player_i, player_j+1))\n            return res\n                    \n        def can_player_access_cell(cell_i, cell_j, box_i, box_j, player_i, player_j):\n            if grid[cell_i][cell_j]=='#':\n                return False\n            q=deque()\n            visited=set()\n            q.append((player_i, player_j))\n            visited.add((player_i, player_j))\n            while q:\n                size=len(q)\n                for i in range(size):\n                    pop=q.popleft()\n                    if pop==(cell_i,cell_j):\n                        return True\n                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):\n                        if nex not in visited:\n                            q.append(nex)\n                            visited.add(nex)\n            return False \n            \n        def box_moves(state):\n            res=set()\n            print(('state', state))\n            box_i, box_j, player_i, player_j = state[0], state[1], state[2], state[3]\n            print(('box_i',box_i))\n            # 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\n            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\n                res.add((box_i+1, box_j, box_i, box_j))\n            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\n                res.add((box_i-1, box_j, box_i, box_j))\n            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\n                res.add((box_i, box_j+1, box_i, box_j))\n            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\n                res.add((box_i, box_j-1, box_i, box_j))\n            print(('res', res))\n            return res\n            \n            \n        def start_state():\n            box_i, box_j, player_i, player_j = -1, -1, -1, -1\n            for i in range(len(grid)):\n                for j in range(len(grid[0])):\n                    if grid[i][j]=='B':\n                        box_i, box_j = i, j\n                    elif grid[i][j]=='S':\n                        player_i, player_j = i, j\n            return (box_i, box_j, player_i, player_j)\n                \n        q=deque()\n        visited=set()\n        start=start_state()\n        q.append(start)\n        visited.add(start)\n        moves=-1\n        while q:\n            size=len(q)\n            print(size)\n            print(q)\n            moves +=1\n            \n            for i in range(size):\n                pop=q.popleft()\n                print(('pop', pop))\n                if grid[pop[0]][pop[1]]=='T':\n                    return moves\n                    \n                for nx in box_moves(pop):\n                    print(('nx',nx))\n                    \n                    if nx not in visited:\n                        q.append(nx)\n                        visited.add(nx)\n                    \n        return -1\n        \n                \n                \n                \n                \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        M, N = len(grid), len(grid[0])\n        for i in range(M):\n            for j in range(N):\n                if grid[i][j] in ['#', '.']:\n                    continue\n                if grid[i][j] == 'S':\n                    player = (i, j)\n                elif grid[i][j] == 'B':\n                    box = (i, j)\n                else:\n                    target = (i, j)\n\n        def heuristic(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n\n        @functools.lru_cache(None)\n        def reach(player, pos, box):\n            i, j = pos\n            if not (0 <= i < M and 0 <= j < N and grid[i][j] != '#'):\n                return False\n            hp = [player]\n            seen = set([player])\n            while hp:\n                player = heapq.heappop(hp)\n                if player == pos:\n                    return True\n                p0, p1 = player\n                for i, j in [(p0 - 1, p1), (p0 + 1, p1), (p0, p1 - 1), (p0, p1 + 1)]:\n                    if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and (i, j) != box and (i, j) not in seen:\n                        seen.add((i, j))\n                        heapq.heappush(hp, (i, j))\n            return False\n\n        seen = set([(box, player)])\n        hp = [(heuristic(box), 0, box, player)]\n        while hp:\n            _, step, box, player = heapq.heappop(hp)\n            print(box)\n            if box == target:\n                return step\n            b0, b1 = box\n            for i, j in [(b0 - 1, b1), (b0 + 1, b1), (b0, b1 - 1), (b0, b1 + 1)]:\n                if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and ((i, j), player) not in seen and reach(player, (\n                b0 * 2 - i, b1 * 2 - j), box):\n                    seen.add(((i, j), player))\n                    heapq.heappush(hp, (heuristic((i, j)) + step + 1, step + 1, (i, j), box))\n        return -1\n                    \n                \n                \n                \n                \n                \n                \n                \n                \n                \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        # two source bfs\n        def neighbor(r, c):\n            for nr, nc in [[r+1, c], [r, c+1], [r-1,c], [r,c-1]]:\n                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':\n                    yield nr,  nc\n                    \n        def can_reach(worker, target, box):\n            if worker == target:\n                return True\n            if target[0] >= R or target[0] < 0 or target[1] >= C or target[1] < 0 or grid[target[0]][target[1]] == '#':\n                return False\n            \n            start = [worker]\n            end = [target]\n            start_seen = {worker}\n            end_seen = {target}\n            \n            while start and end:\n                n_start = []\n                for node in start:\n                    r, c = node\n                    for nr, nc in neighbor(r, c):\n                        if (nr, nc) in end_seen:\n                            return True\n                        if (nr, nc) != box and (nr, nc) not in start_seen:\n                            start_seen.add((nr, nc))\n                            n_start.append((nr, nc))\n                n_end = []\n                for node in end:\n                    r, c = node\n                    for nr, nc in neighbor(r, c):\n                        if (nr, nc) in start_seen:\n                            return True\n                        if (nr, nc) != box and (nr, nc) not in end_seen:\n                            end_seen.add((nr, nc))\n                            n_end.append((nr, nc))\n                start = n_start\n                end = n_end\n        \n        S, B, T = None, None, None\n        \n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 'S':\n                    S = (r, c)\n                elif grid[r][c] == 'B':\n                    B = (r, c)\n                elif grid[r][c] == 'T':\n                    T = (r, c)\n                    \n        level = [(S, B)]\n        seen = {(S, B)}\n        steps = 0\n        while level:\n            n_level = []\n            for player, box in level:\n                r, c = box\n                for nr, nc in neighbor(r, c):\n                    opp_r, opp_c = 2 * r - nr, 2 * c - nc\n                    if can_reach(player, (opp_r, opp_c), box):\n                        if (nr, nc) == T:\n                            return steps + 1\n                        n_state = (box, (nr, nc))\n                        if n_state not in seen:\n                            seen.add(n_state)\n                            n_level.append(n_state)\n            \n            level = n_level\n            # print(seen, level)\n            steps += 1\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        def player_moves(box_i, box_j, player_i, player_j):\n            res=[]\n            if player_i > 0 and grid[player_i-1][player_j] != '#' and (player_i-1, player_j) != (box_i, box_j):\n                res.append((player_i-1, player_j))\n            if player_i < len(grid)-1 and grid[player_i+1][player_j] != '#' and (player_i+1, player_j) != (box_i, box_j):\n                res.append((player_i+1, player_j))\n            if player_j > 0 and grid[player_i][player_j-1] != '#' and (player_i, player_j-1) != (box_i, box_j):\n                res.append((player_i, player_j-1))    \n            if player_j < len(grid[0])-1 and grid[player_i][player_j+1] != '#' and (player_i, player_j+1) != (box_i, box_j):\n                res.append((player_i, player_j+1))\n            return res\n                    \n        def can_player_access_cell(cell_i, cell_j, box_i, box_j, player_i, player_j):\n            if grid[cell_i][cell_j]=='#':\n                return False\n            qu=deque()\n            visited=set()\n            qu.append((player_i, player_j))\n            visited.add((player_i, player_j))\n            while qu:\n                size=len(qu)\n                for i in range(size):\n                    pop=qu.popleft()\n                    if pop==(cell_i,cell_j):\n                        return True\n                    for nex in player_moves(box_i, box_j, pop[0], pop[1]):\n                        if nex not in visited:\n                            qu.append(nex)\n                            visited.add(nex)\n            return False \n            \n        def box_moves(state):\n            res=set()\n            print(('state', state))\n            box_i, box_j, player_i, player_j = state[0], state[1], state[2], state[3]\n            print(('box_i',box_i))\n            # 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\n            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\n                res.add((box_i+1, box_j, box_i, box_j))\n            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\n                res.add((box_i-1, box_j, box_i, box_j))\n            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\n                res.add((box_i, box_j+1, box_i, box_j))\n            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\n                res.add((box_i, box_j-1, box_i, box_j))\n            print(('res', res))\n            return res\n            \n            \n        def start_state():\n            box_i, box_j, player_i, player_j = -1, -1, -1, -1\n            for i in range(len(grid)):\n                for j in range(len(grid[0])):\n                    if grid[i][j]=='B':\n                        box_i, box_j = i, j\n                    elif grid[i][j]=='S':\n                        player_i, player_j = i, j\n            return (box_i, box_j, player_i, player_j)\n                \n        q=deque()\n        visited=set()\n        start=start_state()\n        q.append(start)\n        visited.add(start)\n        moves=-1\n        #return\n        while q:\n            size=len(q)\n            print(size)\n            print(q)\n            moves +=1\n            \n            for i in range(size):\n                pop=q.popleft()\n                print(('pop', pop))\n                if grid[pop[0]][pop[1]]=='T':\n                    return moves\n                    \n                for nx in box_moves(pop):\n                    print(('nx',nx))\n                    \n                    if nx not in visited:\n                        q.append(nx)\n                        visited.add(nx)\n                    \n        return -1\n        \n                \n                \n                \n                \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'S':\n                    si, sj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    ti, tj = i, j\n                    grid[i][j] = '.'\n        q = [(bi, bj, si, sj, 0)]\n        seen = {(bi, bj, si, sj)}\n        while q:\n            bi, bj, si, sj, dist = q.pop(0)\n            if (bi, bj) == (ti, tj):\n                return dist\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                si_new, sj_new = bi+dx, bj+dy\n                bi_new, bj_new = bi-dx, bj-dy\n                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] == '.':\n                    q.append((bi_new, bj_new, bi, bj, dist+1))\n                    seen.add((bi_new, bj_new, bi, bj))\n        return -1\n    \n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            if si == si_new and sj == sj_new:\n                return True\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return False\n    '''\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):\n        m, n = len(grid), len(grid[0])\n        if si == si_new and sj == sj_new:\n            return True\n        visited.add((si, sj))\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            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):\n                return True\n        return False\n        \n    def canMoveTo(self, grid, bi, bj, si, sj, validSet):\n        m, n = len(grid), len(grid[0])\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            if (i, j) in validSet:\n                continue\n            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                validSet.add((i, j))\n                self.canMoveTo(grid, bi, bj, i, j, validSet)\n        return validSet\n    '''    ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        cache = {}\n        visited = set()\n        def dp(b, p):\n            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:\n                return float(\\\"inf\\\")\n            if grid[b[0]][b[1]] == 'T':\n                return 0\n            if (b, p) in cache:\n                return cache[(b, p)]\n            if (b, p) in visited:\n                return float(\\\"inf\\\")\n            visited.add((b, p))\n            ans = float(\\\"inf\\\")\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)\n            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))))\n            visited.remove((b, p))\n            cache[(b, p)] = ans\n            return ans\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n        ans = dp(b, p)\n        print(cache)\n        return -1 if ans == float(\\\"inf\\\") else ans\n    \n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        q = collections.deque()\n        visited = set()\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n                    \n        q.append((b, p, 0))\n        visited.add((b, p))\n        while q:\n            b, p, c = q.popleft()\n            if grid[b[0]][b[1]] == 'T':\n                return c\n            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):\n                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:\n                    q.appendleft((b, pp, c))\n                    visited.add((b, pp))\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                p = b\n                b = (b[0]+delta[0], b[1]+delta[1])\n                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':\n                    q.append((b, p, c+1))\n                    visited.add((b, p))\n        return -1\n            \n            ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'S':\n                    si, sj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    ti, tj = i, j\n                    grid[i][j] = '.'\n        q = [(bi, bj, si, sj, 0)]\n        seen = {(bi, bj, si, sj)}\n        while q:\n            bi, bj, si, sj, dist = q.pop(0)\n            if (bi, bj) == (ti, tj):\n                return dist\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                si_new, sj_new = bi+dx, bj+dy\n                bi_new, bj_new = bi-dx, bj-dy\n                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] == '.':\n                    q.append((bi_new, bj_new, bi, bj, dist+1))\n                    seen.add((bi_new, bj_new, bi, bj))\n        return -1\n    \n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            if si == si_new and sj == sj_new:\n                return True\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return False\n    '''\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):\n        m, n = len(grid), len(grid[0])\n        if si == si_new and sj == sj_new:\n            return True\n        visited.add((si, sj))\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            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):\n                return True\n        return False\n\n    def canMoveTo(self, grid, bi, bj, si, sj, validSet):\n        m, n = len(grid), len(grid[0])\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            if (i, j) in validSet:\n                continue\n            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                validSet.add((i, j))\n                self.canMoveTo(grid, bi, bj, i, j, validSet)\n        return validSet\n    '''    ", "class Solution:\n    def minPushBox(self, A: List[List[str]]) -> int:\n        if not A: return -1\n\n        rows, cols = len(A), len(A[0])\n        box = end = dude = None\n        \n        for row in range(rows):\n            for col in range(cols):\n                if A[row][col] == 'B':   box = (row, col)\n                elif A[row][col] == 'T': end = (row, col)\n                elif A[row][col] == 'S': npc = (row, col)  \n        \n        def bfs(start, end, blocked):\n            cache, q = set(start), collections.deque([start])\n            while q:\n                i, j = q.popleft()\n                if (i, j) == end:\n                    return True\n                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n                    row, col = i + di, j + dj\n                    if 0 <= row < rows and 0 <= col < cols and \\\\\n                       (row, col) not in cache and A[row][col] != '#' and \\\\\n                       (row, col) != blocked:\n                        q.append((row, col))\n                        cache.add((row, col))\n            return False\n                \n        visited, q = set([(box, npc)]), collections.deque([(box, npc, 0)])\n        while q:\n            (i, j), player, moves = q.popleft()\n            if (i, j) == end:\n                return moves\n            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n                row, col = i + di, j + dj\n                if 0 <= row < rows and 0 <= col < cols and ((row, col), (i, j)) not in visited and A[row][col] != '#':\n                    if bfs(player, (i - di, j - dj), (i, j)):\n                        q.append(((row, col), (i, j), moves + 1))\n                        visited.add(((row, col), (i, j)))\n        return -1\n                    ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        self.empty = [['.' for _ in range(n)] for _ in range(m)]\n        for i, row in enumerate(grid):\n            for j, c in enumerate(row):\n                if c == 'B': start = (i,j)\n                if c == 'S': player = (i,j)\n                if c == 'T': target = (i,j)\n                if c == '#': self.empty[i][j] = '#'\n        visit = [[0 for _ in range(n)] for _ in range(m)]\n        visit[start[0]][start[1]] += 1\n        deq = collections.deque([(start,player,(-1,-1))])\n        push = 0\n        paths = dict()\n        while deq and push < m * n:\n            sz = len(deq)\n            for i in range(sz):\n                box,player, previous = deq.popleft()\n                if box == target: return push\n                cango = paths[(player,box)] if (player,box) in paths else self.player(player, box,self.empty)\n                paths[(player,box)] = cango\n                for d in self.direction:\n                    nr, nc = box[0] + d[0], box[1] + d[1]\n                    pr,pc = box[0] + d[2], box[1] + d[3]\n                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:\n                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:\n                            visit[nr][nc] +=1\n                            deq.append(((nr,nc),(pr,pc),box))\n            push += 1\n        return -1\n    \n    def player(self, player, box, grid):\n        m, n = len(grid), len(grid[0])\n        visit = [[False for _ in range(n)] for _ in range(m)]\n        visit[player[0]][player[1]] = True\n        deq = collections.deque([player])\n        while deq:\n            sz = len(deq)\n            for i in range(sz):\n                cur = deq.popleft()\n                for d in self.direction:\n                    nr, nc = cur[0] + d[0], cur[1] + d[1]\n                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):\n                        visit[nr][nc] = True\n                        deq.append((nr,nc))\n        return visit\n    \n    def __init__(self):\n        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))\n        self.empty = None", "class Solution:\n    def minPushBox(self, A: List[List[str]]) -> int:\n        if not A: return -1\n\n        rows, cols = len(A), len(A[0])\n        box = end = dude = None\n        \n        for row in range(rows):\n            for col in range(cols):\n                if A[row][col] == 'B':   box = (row, col)\n                elif A[row][col] == 'T': end = (row, col)\n                elif A[row][col] == 'S': npc = (row, col)  \n        \n        def bfs(start, end, blocked):\n            cache, q = set(start), collections.deque([start])\n            while q:\n                i, j = q.popleft()\n                if (i, j) == end:\n                    return True\n                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n                    row, col = i + di, j + dj\n                    if 0 <= row < rows and 0 <= col < cols and \\\\\n                       (row, col) not in cache and A[row][col] != '#' and \\\\\n                       (row, col) != blocked:\n                        q.append((row, col))\n                        cache.add((row, col))\n            return False\n                \n        visited, q = set([(box, npc)]), collections.deque([(box, npc, 0)])\n        while q:\n            (i, j), player, moves = q.popleft()\n            if (i, j) == end:\n                return moves\n            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n                row, col = i + di, j + dj\n                if 0 <= row < rows and 0 <= col < cols and ((row, col), (i, j)) not in visited and A[row][col] != '#':\n                    if bfs(player, (i - di, j - dj), (i, j)):\n                        q.append(((row, col), (i, j), moves + 1))\n                        visited.add(((row, col), (i, j)))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        ## from https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/bfsbfs-by-haitao-yu/\n        ## \u53cc BFS\n        directions = [(1,0),(-1,0),(0,1),(0,-1)]\n        M = len(grid)\n        N = len(grid[0])\n    \n        def find_target(target):\n            row,col = None, None\n            for i in range(len(grid)):\n                for j in range(len(grid[0])):\n                    if grid[i][j] == target:\n                        row, col = i,j\n                        break\n            return row, col\n        \n        def check_pos_valid(i,j):\n            if i >=0 and i < M and j >= 0 and j < N and grid[i][j] in [\\\"T\\\",\\\".\\\"]:\n                return True\n            else :\n                return False\n    \n        def player_bfs(player_x,player_y, behind_box_x,behind_box_y):\n            \n            queue = [(player_x,player_y)]\n            visited = set()\n    \n            while len(queue) !=0:\n                player_x,player_y = queue.pop(0)\n                visited.add((player_x,player_y))\n                \n                if (player_x,player_y) == (behind_box_x,behind_box_y):\n                    return True\n                \n                for dx,dy in directions:\n                    next_x = player_x + dx\n                    next_y = player_y + dy\n                    if check_pos_valid(next_x, next_y) and (next_x, next_y) not in visited:\n                        queue.append( (next_x, next_y) )\n                        visited.add( (next_x, next_y) )\n            return False\n    \n    \n    \n        box_x,box_y = find_target(\\\"B\\\")\n        player_x,player_y = find_target(\\\"S\\\")\n        end_x, end_y = find_target(\\\"T\\\")\n        init_state = (box_x,box_y, player_x,player_y,0)\n        queue = [init_state]\n        visited = set()\n        visited.add((box_x,box_y, player_x,player_y))\n    \n        ## \u6e05\u9664 B \u548c S\n        grid[box_x][box_y] = \\\".\\\"\n        grid[player_x][player_y] = \\\".\\\"\n    \n    \n        # ## BFS #1\n        while len(queue) !=0 :\n            # print(queue)\n            box_x,box_y, player_x,player_y, step  = queue.pop(0)\n            # visited.add((box_x,box_y, player_x,player_y))  \u5c06\u65f6\n            \n            ## \u68c0\u67e5\u7bb1\u5b50\u72b6\u6001\n            if (box_x, box_y) == (end_x, end_y):\n                return step\n            \n            ## \u66f4\u65b0\u7bb1\u5b50\u7684\u4f4d\u7f6e\n            grid[box_x][box_y] = \\\"B\\\"  ## B \u662f\u53ef\u4ee5\u6321\u8def\u7684\uff0c\u5bfc\u81f4 player \u65e0\u6cd5\u7ed5\u5230\u7bb1\u5b50\u540e\u3002\u5728\u5bf9 player bfs \u65f6\u9700\u8981\u8003\u8651\uff0c\u56e0\u6b64\u7f6e\u4e4b\u4e3a B\n            for dx,dy in directions:\n                ## \u7bb1\u5b50\u7684\u4e0b\u4e00\u4e2a\u53ef\u80fd\u7684\u4f4d\u7f6e\n                box_next_x = box_x + dx\n                box_next_y = box_y + dy\n                if check_pos_valid(box_next_x, box_next_y):\n                    ## \u5982\u679c\u7bb1\u5b50\u7684\u4e0b\u4e00\u4e2a\u53ef\u80fd\u4f4d\u7f6e\u5408\u6cd5\uff0c\u5219\u68c0\u67e5\u5f53\u524d\u7bb1\u5b50\u7684\u540e\u65b9\u4f4d\u7f6e\u662f\u5426\u5408\u6cd5\uff08\u5408\u6cd5\u7684\u8bdd\uff0c\u7bb1\u5b50\u624d\u53ef\u80fd\u79fb\u52a8\u5230\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff09\n                    behind_box_x = box_x - dx\n                    behind_box_y = box_y - dy\n                    if check_pos_valid(behind_box_x, behind_box_y):\n                        ## \u540e\u65b9\u4f4d\u7f6e\u4e5f\u5408\u6cd5\uff0c\u68c0\u67e5 player \u662f\u5426\u80fd\u8d70\u5230\u8be5\u4f4d\u7f6e(\u53ef\u4ee5\u4f7f\u7528 bfs)\n                        if player_bfs(player_x,player_y, behind_box_x,behind_box_y):\n                            ## \u5982\u679c\u53ef\u4ee5\u8d70\u5230\uff0c\u4e14\u5f53\u524d\u4f4d\u7f6e\u672a\u8bbf\u95ee\uff0c\u5219\u52a0\u5165\u961f\u5217\n                            next_state = (box_next_x, box_next_y, behind_box_x, behind_box_y, step+1)\n                            if (box_next_x, box_next_y, behind_box_x, behind_box_y) not in visited:\n                                queue.append(next_state)\n                                visited.add((box_next_x, box_next_y, behind_box_x, behind_box_y))\n            grid[box_x][box_y] = \\\".\\\"\n        return -1   ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        ## from https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/bfsbfs-by-haitao-yu/\n        ## \u53cc BFS\n        directions = [(1,0),(-1,0),(0,1),(0,-1)]\n        M = len(grid)\n        N = len(grid[0])\n    \n        def find_target(target):\n            row,col = None, None\n            for i in range(len(grid)):\n                for j in range(len(grid[0])):\n                    if grid[i][j] == target:\n                        row, col = i,j\n                        break\n            return row, col\n        \n        def check_pos_valid(i,j):\n            if i >=0 and i < M and j >= 0 and j < N and grid[i][j] in [\\\"T\\\",\\\".\\\"]:\n                return True\n            else :\n                return False\n    \n        def player_bfs(player_x,player_y, behind_box_x,behind_box_y):\n            \n            queue = [(player_x,player_y)]\n            visited = set()\n    \n            while len(queue) !=0:\n                player_x,player_y = queue.pop(0)\n                visited.add((player_x,player_y))\n                \n                if (player_x,player_y) == (behind_box_x,behind_box_y):\n                    return True\n                \n                for dx,dy in directions:\n                    next_x = player_x + dx\n                    next_y = player_y + dy\n                    if check_pos_valid(next_x, next_y) and (next_x, next_y) not in visited:\n                        queue.append( (next_x, next_y) )\n                        visited.add( (next_x, next_y) )\n            return False\n    \n    \n    \n        box_x,box_y = find_target(\\\"B\\\")\n        player_x,player_y = find_target(\\\"S\\\")\n        end_x, end_y = find_target(\\\"T\\\")\n        init_state = (box_x,box_y, player_x,player_y,0)\n        queue = [init_state]\n        visited = set()\n        visited.add((box_x,box_y, player_x,player_y))\n    \n        ## \u6e05\u9664 B \u548c S\n        grid[box_x][box_y] = \\\".\\\"\n        grid[player_x][player_y] = \\\".\\\"\n    \n    \n        # ## BFS #1\n        while len(queue) !=0 :\n            # print(queue)\n            box_x,box_y, player_x,player_y, step  = queue.pop(0)\n            \n            ## \u68c0\u67e5\u7bb1\u5b50\u72b6\u6001\n            if (box_x, box_y) == (end_x, end_y):\n                return step\n            \n            ## \u66f4\u65b0\u7bb1\u5b50\u7684\u4f4d\u7f6e\n            grid[box_x][box_y] = \\\"B\\\"  ## B \u662f\u53ef\u4ee5\u6321\u8def\u7684\uff0c\u5bfc\u81f4 player \u65e0\u6cd5\u7ed5\u5230\u7bb1\u5b50\u540e\u3002\u5728\u5bf9 player bfs \u65f6\u9700\u8981\u8003\u8651\uff0c\u56e0\u6b64\u7f6e\u4e4b\u4e3a B\n            for dx,dy in directions:\n                ## \u7bb1\u5b50\u7684\u4e0b\u4e00\u4e2a\u53ef\u80fd\u7684\u4f4d\u7f6e\n                box_next_x = box_x + dx\n                box_next_y = box_y + dy\n                if check_pos_valid(box_next_x, box_next_y):\n                    ## \u5982\u679c\u7bb1\u5b50\u7684\u4e0b\u4e00\u4e2a\u53ef\u80fd\u4f4d\u7f6e\u5408\u6cd5\uff0c\u5219\u68c0\u67e5\u5f53\u524d\u7bb1\u5b50\u7684\u540e\u65b9\u4f4d\u7f6e\u662f\u5426\u5408\u6cd5\uff08\u5408\u6cd5\u7684\u8bdd\uff0c\u7bb1\u5b50\u624d\u53ef\u80fd\u79fb\u52a8\u5230\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff09\n                    behind_box_x = box_x - dx\n                    behind_box_y = box_y - dy\n                    if check_pos_valid(behind_box_x, behind_box_y):\n                        ## \u540e\u65b9\u4f4d\u7f6e\u4e5f\u5408\u6cd5\uff0c\u68c0\u67e5 player \u662f\u5426\u80fd\u8d70\u5230\u8be5\u4f4d\u7f6e(\u53ef\u4ee5\u4f7f\u7528 bfs)\n                        if player_bfs(player_x,player_y, behind_box_x,behind_box_y):\n                            ## \u5982\u679c\u53ef\u4ee5\u8d70\u5230\uff0c\u4e14\u5f53\u524d\u4f4d\u7f6e\u672a\u8bbf\u95ee\uff0c\u5219\u52a0\u5165\u961f\u5217\n                            next_state = (box_next_x, box_next_y, behind_box_x, behind_box_y, step+1)\n                            if (box_next_x, box_next_y, behind_box_x, behind_box_y) not in visited:\n                                queue.append(next_state)\n                                visited.add((box_next_x, box_next_y, behind_box_x, behind_box_y))\n            grid[box_x][box_y] = \\\".\\\"\n        return -1   ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        \n        def nxt(pos):\n            r, c = pos\n            res = []\n            for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:\n                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':\n                    res.append((nr, nc))\n            return res\n        \n        def connected(p, q, box):\n            queue = collections.deque([p])\n            seen = set()\n            while queue:\n                node = queue.popleft()\n                for nr, nc in nxt(node):\n                    if (nr, nc) != box:\n                        if (nr, nc) == q:\n                            return True\n                        if (nr, nc) not in seen:\n                            seen.add((nr, nc))\n                            queue.append((nr, nc))\n            return False\n                \n        target, box, worker = None, None, None\n        \n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 'S':\n                    worker = (r, c)\n                if grid[r][c] == 'B':\n                    box = (r, c)\n                if grid[r][c] == 'T':\n                    target = (r, c)\n        \n        level = []\n        seen = set()\n        for pos in nxt(box):\n            #print(pos)\n            if connected(pos, worker, box):\n                level.append((box, pos))\n                seen.add((box, pos))\n                \n        grid[box[0]][box[1]] = '.'\n        steps = 0\n        \n        while level:\n            n_level = []\n            for b, w in level:\n                candi = nxt(b)\n                for pos in candi:\n                    nb = (2 * b[0] - pos[0], 2 * b[1] - pos[1])\n                    if nb == target:\n                        return steps + 1\n                    if nb in candi and (nb, b) not in seen and connected(w, pos, b):\n                        seen.add((nb, b))\n                        n_level.append((nb, b))\n            steps += 1\n            level = n_level\n        \n        return -1\n", "class Solution:\n    # DFS failed\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        cache = {}\n        visited = set()\n        def dp(b, p):\n            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:\n                return float(\\\"inf\\\")\n            if grid[b[0]][b[1]] == 'T':\n                return 0\n            if (b, p) in cache:\n                return cache[(b, p)]\n            if (b, p) in visited:\n                return float(\\\"inf\\\")\n            visited.add((b, p))\n            ans = float(\\\"inf\\\")\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)\n            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))))\n            visited.remove((b, p))\n            cache[(b, p)] = ans\n            return ans\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n        ans = dp(b, p)\n        print(cache)\n        return -1 if ans == float(\\\"inf\\\") else ans\n    \n    # BFS\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        q = collections.deque()\n        visited = set()\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n                    \n        q.append((b, p, 0))\n        visited.add((b, p))\n        while q:\n            b, p, c = q.popleft()\n            if grid[b[0]][b[1]] == 'T':\n                return c\n            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):\n                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:\n                    q.appendleft((b, pp, c))\n                    visited.add((b, pp))\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                p = b\n                b = (b[0]+delta[0], b[1]+delta[1])\n                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':\n                    q.append((b, p, c+1))\n                    visited.add((b, p))\n        return -1\n            \n            ", "class Solution:\n    def minPushBox(self, grid) -> int:\n        T = B = S = (-1, -1)\n        l = len(grid)\n        w = len(grid[0])\n        for i in range(l):\n            for j in range(w):\n                if grid[i][j] == 'T':\n                    T = (i, j)\n                elif grid[i][j] == 'B':\n                    B = (i, j)\n                elif grid[i][j] == 'S':\n                    S = (i, j)\n\n        directions = [0, -1, 0, 1, 0]\n        q = [B + S]\n        visited = set()\n        steps = 0\n        self.next_step = (-1, -1, -1, -1)\n\n        def is_pushable(cur_bs, dx, dy):\n            bx, by, sx, sy = cur_bs\n            nbx = bx + dx\n            nby = by + dy\n            nsx = bx - dx\n            nsy = by - dy\n            if is_valid(nbx, nby) and is_valid(nsx, nsy):\n                if is_reachable(sx, sy, nsx, nsy, bx, by):\n                    self.next_step = (nbx, nby, nsx, nsy)\n                    return True\n            return False\n\n        def is_valid(nx, ny):\n            return 0 <= nx < l and 0 <= ny < w and grid[nx][ny] != '#'\n\n        def is_reachable(sx, sy, nsx, nsy, cur_bx, cur_by):\n            queue = [(sx, sy)]\n            visited_set = set()\n            while queue:\n                cur_s = queue.pop(0)\n                if cur_s not in visited_set and cur_s != (cur_bx, cur_by):\n                    visited_set.add(cur_s)\n                    if cur_s == (nsx, nsy):\n                        return True\n                    cx, cy = cur_s\n                    for idx in range(4):\n                        dx, dy = directions[idx], directions[idx + 1]\n                        nx, ny = cx + dx, cy + dy\n                        if is_valid(nx, ny):\n                            queue.append((nx, ny))\n            return False\n\n        while q:\n            tmp = []\n            for cur in q:\n                if cur not in visited:\n                    visited.add(cur)\n                    for i in range(4):\n                        dir_x, dir_y = directions[i], directions[i + 1]\n                        if is_pushable(cur, dir_x, dir_y):\n                            box_x, box_y, _, _ = self.next_step\n                            if (box_x, box_y) == T:\n                                return steps + 1\n                            tmp.append(self.next_step)\n            q = tmp\n            steps += 1\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        rows, cols = len(grid), len(grid[0])\n        \n        \n        br,bc = -1,-1\n        sr,sc = -1,-1\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == 'B':\n                    br, bc = r,c\n                elif grid[r][c] == 'S':\n                    sr, sc = r,c\n                    \n                    \n        \n        def reachable(br,bc, sr,sc,tr,tc):\n            visited = {(sr,sc)}\n            def helper(curr, curc):\n                if curr == tr and curc == tc:\n                    return True\n                for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:\n                    newr,newc = curr+dr, curc+dc\n                    if newr < 0 or newr >= rows or newc < 0 or newc >= cols: continue\n                    if grid[newr][newc] == '#' or (newr,newc) == (br,bc): continue\n                    if (newr,newc) in visited: continue\n                    visited.add((newr,newc))\n                    if helper(newr,newc): return True\n                return False\n            return helper(sr,sc)\n                        \n        \n        \n        seen = {(br,bc,sr,sc)}\n        step = 0\n        frontier = [(br,bc,sr,sc)]\n        while frontier:\n            newft = []\n            for br,bc,sr,sc in frontier:\n                if grid[br][bc] == 'T': return step\n                \n                for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:\n                    newr,newc = br+dr, bc+dc\n                    if newr < 0 or newr >= rows or newc < 0 or newc >= cols: continue\n                    if grid[newr][newc] == '#': continue\n                    targr,targc = br-dr,bc-dc\n                    if targr < 0 or targr >= rows or targc < 0 or targc >= cols: continue\n                    if grid[targr][targc] == '#': continue\n                    if (newr,newc,targr,targc) in seen: continue\n                    if not reachable(br,bc, sr,sc,targr,targc): continue\n                    seen.add((newr,newc, targr,targc))\n                    newft.append((newr,newc, targr,targc))\n                    \n            step+=1\n            frontier = newft\n                    \n                    \n        return -1\n                \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        if not grid or not grid[0]:\n            return -1\n        \n        # Main idea: run Dijkstra's except only expand on nodes\n        # that do not have a wall on the oposite side of the\n        # box location. Also check for each position if we can\n        # get from the old starting location to the new appropriate\n        # push position\n        \n        self.grid = grid\n        self.memo = {} # (start => dst) : True or False by DFS'ing\n        dst = None\n        start = None\n        box_start = None\n        from queue import Queue\n        pq = Queue()\n        for row in range(len(grid)):\n            for col in range(len(grid[row])):\n                elem = grid[row][col]\n                if elem == \\\"B\\\":\n                    box_start = (row, col)\n                elif elem == \\\"T\\\":\n                    dst = (row, col)\n                elif elem == \\\"S\\\":\n                    start = (row, col)\n        \n        assert dst is not None\n        assert start is not None\n        assert box_start is not None\n        pq.put((0, box_start[0], box_start[1], start))\n        \n        best = set()\n        while not pq.empty():\n            pushes, row, col, start = pq.get()\n            if (row, col, start) not in best:\n                best.add((row, col, start))\n                if (row, col) == dst:\n                    return pushes\n                if row + 1 < len(grid) and row - 1 >= 0:\n                    if grid[row + 1][col] != \\\"#\\\" and grid[row - 1][col] != \\\"#\\\" and self.dfs(start[0], start[1], (row +1, col), set(), (row, col)):\n                        pq.put((pushes + 1, row - 1, col, (row, col)))\n                    if grid[row - 1][col] != \\\"#\\\" and grid[row + 1][col] != \\\"#\\\" and self.dfs(start[0], start[1], (row - 1, col), set(), (row, col)):\n                        pq.put((pushes + 1, row + 1, col, (row, col)))\n                if col + 1 < len(grid[0]) and col - 1 >= 0:\n                    if grid[row][col + 1] != \\\"#\\\" and grid[row][col - 1] != \\\"#\\\" and self.dfs(start[0], start[1], (row , col + 1), set(), (row, col)):\n                        pq.put((pushes + 1, row, col - 1, (row, col)))\n                    if grid[row][col - 1] != \\\"#\\\" and grid[row][col + 1] != \\\"#\\\" and self.dfs(start[0], start[1], (row , col - 1), set(), (row, col)):\n                        pq.put((pushes + 1, row, col + 1, (row, col)))\n        return -1\n    \n    def dfs(self, r, c, goal, seen, box_location):\n        if ((r, c), goal) in self.memo:\n            return self.memo[(r, c), goal]\n        if (r, c) == goal:\n            return True\n        if not (0 <= r < len(self.grid)):\n            return False\n        if not (0 <= c < len(self.grid[0])):\n            return False\n        if self.grid[r][c] == \\\"#\\\":\n            return False\n        if (r, c) == box_location:\n            return False\n        if (r, c) not in seen:\n            seen.add((r, c))\n            if self.dfs(r + 1, c, goal, seen, box_location):\n                self.memo[((r, c), goal)] = True\n                return True\n            if self.dfs(r - 1, c, goal, seen, box_location):\n                self.memo[((r, c), goal)] = True\n                return True\n            if self.dfs(r, c + 1, goal, seen, box_location):\n                self.memo[((r, c), goal)] = True\n                return True\n            if self.dfs(r, c - 1, goal, seen, box_location):\n                self.memo[((r, c), goal)] = True\n                return True\n        self.memo[((r, c), goal)] = False\n        return False", "import heapq\nclass Solution: \n    def est_distance(self, grid, target_posi, box_posi, move):\n        return move + abs(target_posi[0] - box_posi[0]) + abs(target_posi[1] - box_posi[1])\n    \n    def isvalid_posi(self, grid, m, n, posi):\n        i, j = posi\n        if i<0 or i>=m or j<0 or j>=n:\n            return False\n        return grid[i][j] != '#'\n    \n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        m = len(grid)\n        n = len(grid[0])\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    box_posi = (i,j)\n                if grid[i][j] == 'T':\n                    target_posi = (i,j)\n                if grid[i][j] == 'S':\n                    start_posi = (i,j)\n        \n        seen = set()\n        seen.add((box_posi, start_posi))\n        \n        init_dist = self.est_distance(grid, target_posi, box_posi, 0)\n        heap = [(init_dist, 0, box_posi, start_posi)]\n        \n        while heap:\n            dist, move, current_box, current_human =  heapq.heappop(heap)\n            if current_box == target_posi:\n                return move\n            for row_move, col_move in [(-1,0), (1,0),(0,1),(0,-1)]:\n                new_human = (current_human[0] + row_move, current_human[1] + col_move)\n                if not self.isvalid_posi(grid, m, n, new_human):\n                    continue\n                if (current_box, new_human) not in seen:\n                    if new_human == current_box:\n                        new_box = (current_box[0] + row_move, current_box[1] + col_move)\n                        if self.isvalid_posi(grid, m, n, new_box):\n                            seen.add((new_box, new_human))\n                            new_dist = self.est_distance(grid, target_posi, new_box, move+1)\n                            heapq.heappush(heap, (new_dist, move + 1, new_box, new_human))\n                    else:\n                        seen.add((current_box, new_human))\n                        new_dist = self.est_distance(grid, target_posi, current_box, move)\n                        heapq.heappush(heap, (new_dist, move, current_box, new_human))\n        \n        \n        return -1\n                        \n                            \n                        \n        \n        \n", "class Solution:\n    def minPushBox(self, A: List[List[str]]) -> int:\n        \n        def reachable(sx, sy, tsx, tsy, bx, by, A, dirs):\n            m, n = len(A), len(A[0])\n            visited = [[0] * 20 for _ in range(20)]\n            visited[sx][sy] = 1\n            q = deque()\n            q.append([sx, sy])\n            while q:\n                sx, sy = q.popleft()\n                for dx, dy in dirs:\n                    nsx, nsy = sx + dx, sy + dy\n                    if 0 <= nsx < m and 0 <= nsy < n and visited[nsx][nsy] == 0 and (A[nsx][nsy] in '.T' and [nsx, nsy] != [bx, by]):\n                        if [nsx, nsy] == [tsx, tsy]: return True\n                        visited[nsx][nsy] = 1\n                        q.append([nsx, nsy])\n            return False\n        \n        m, n = len(A), len(A[0])\n        \n        for i in range(m):\n            for j in range(n):\n                if A[i][j] == 'B':\n                    bx, by = i, j\n                    A[i][j] = '.'\n                if A[i][j] == 'S':\n                    sx, sy = i, j\n                    A[i][j] = '.'\n        dirs = [[-1,0],[1,0],[0,-1],[0,1]]\n        visited = [[0] * 400 for _ in range(400)]\n        visited[bx*20+by][sx*20+sy] = 1\n        \n        q = deque()\n        q.append([bx, by, sx, sy, 0])\n        \n        while q:\n            # print(q)\n            bx, by, sx, sy, step = q.popleft()\n            for dx, dy in dirs:\n                nbx, nby = bx + dx, by + dy\n                if 0 <= nbx < m and 0 <= nby < n and A[nbx][nby] in '.T':\n                    nsx, nsy = 2 * bx - nbx, 2 * by - nby\n                    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:\n                        if A[nbx][nby] == 'T': return step + 1\n                        visited[nbx*20+nby][nsx*20+nsy] = 1\n                        q.append([nbx,nby,nsx,nsy,step+1])\n        return -1\n", "class Solution:\n    # DFS failed\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        cache = {}\n        visited = set()\n        def dp(b, p):\n            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:\n                return float(\\\"inf\\\")\n            if grid[b[0]][b[1]] == 'T':\n                return 0\n            if (b, p) in cache:\n                return cache[(b, p)]\n            if (b, p) in visited:\n                return float(\\\"inf\\\")\n            visited.add((b, p))\n            ans = float(\\\"inf\\\")\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                ans = 1+dp((b[0]+delta[0], b[1]+delta[1]), b)\n            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))))\n            visited.remove((b, p))\n            cache[(b, p)] = ans\n            return ans\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n        ans = dp(b, p)\n        print(cache)\n        return -1 if ans == float(\\\"inf\\\") else ans\n    \n    # BFS\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        q = collections.deque()\n        visited = set()\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n                    \n        q.append((b, p, 0))\n        visited.add((b, p))\n        while q:\n            b, p, c = q.popleft()\n            if grid[b[0]][b[1]] == 'T':\n                return c\n            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):\n                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:\n                    q.appendleft((b, pp, c))\n                    visited.add((b, pp))\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                p = b\n                b = (b[0]+delta[0], b[1]+delta[1])\n                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':\n                    q.append((b, p, c+1))\n                    visited.add((b, p))\n        return -1\n    \n    # BFS + A*\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        from heapq import heappop, heappush\n        \n        q = []\n        visited = set()\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    p = (i, j)\n                if grid[i][j] == 'T':\n                    t = (i, j)\n                \n                    \n        q.append((abs(t[0]-b[0]) + abs(t[1]-b[1]), 0, b, p))\n        visited.add((b, p))\n        while q:\n            gh, g, b, p = heappop(q)\n            if b == t:\n                return g\n            for pp in ((p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)):\n                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:\n                    heappush(q, (gh, g, b, pp))\n                    visited.add((b, pp))\n            if abs(b[0] - p[0]) + abs(b[1] - p[1]) == 1:\n                delta = (b[0] - p[0], b[1] - p[1])\n                p = b\n                b = (b[0]+delta[0], b[1]+delta[1])\n                if (b, p) not in visited and 0<=b[0]<m and 0<=b[1]<n and grid[b[0]][b[1]] != '#':\n                    heappush(q, (g+1+abs(t[0]-b[0]) + abs(t[1]-b[1]), g+1, b, p))\n                    visited.add((b, p))\n        return -1\n            \n            ", "from heapq import heappush, heappop\nclass Solution:\n    def minPushBox(self, A: List[List[str]]) -> int:\n        m, n = len(A), len(A[0])\n        for i in range(m):\n            for j in range(n):\n                if A[i][j] == 'B':\n                    b_pos = (i, j)\n                elif A[i][j] == 'T':\n                    t_pos = (i, j)\n                elif A[i][j] == 'S':\n                    p_pos = (i, j)\n        \n        def estimate(pos):\n            return abs(t_pos[0] - pos[0]) + abs(t_pos[1] - pos[1])\n        seen = {(p_pos, b_pos)}\n        heap = [[estimate(b_pos), 0, p_pos, b_pos]]\n        nbs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n        while heap:\n            est, cost, person, box = heappop(heap)\n            if box == t_pos:\n                return cost\n            for a, b in nbs:\n                x, y = person[0] + a, person[1] + b\n                if 0 <= x < m and 0 <= y < n and A[x][y] != '#':\n                    n_person = (x, y)\n                    n_box = box\n                    n_cost = cost\n                    if n_person == box:\n                        n_box = (x + a, y + b)\n                        n_cost += 1\n                    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:\n                        heappush(heap, [estimate(n_box) + n_cost, n_cost, n_person, n_box])\n                        seen.add((n_person, n_box))\n        return -1\n", "from collections import deque \nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        def check(sx, sy, px, py):\n            q = deque([(px, py)])\n            visited = set((px, py))\n            while q:\n                x, y = q.popleft()\n                if (x, y) == (sx, sy):\n                    return True\n                for dx, dy in (-1, 0), (0,-1), (0,1), (1,0):\n                    x_, y_ = x+dx, y+dy\n                    if valid(x_, y_) and (x_,y_) not in visited:\n                        visited.add((x_, y_))\n                        q.append((x_, y_))\n            return False\n        \n        def valid(x_, y_):\n            return 0<=x_<m and 0<=y_<n and grid[x_][y_] ==\\\".\\\"\n        \n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"B\\\":\n                    bx, by = i, j\n                    grid[i][j] = \\\".\\\"\n                if grid[i][j] == \\\"S\\\":\n                    sx, sy = i, j\n                    grid[i][j] = \\\".\\\"\n                if grid[i][j] == \\\"T\\\":\n                    tx, ty = i, j\n                    \n        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))])\n        visited = set()\n        level = 0\n        while q:\n            level += 1\n            print(q)\n            for _ in range(len(q)):\n                \n                bx, by, x, y = q.popleft()\n\n                visited.add((bx, by, x, y))\n                x_, y_ = bx-x, by-y\n                if (x_, y_) == (tx, ty):\n                    return level\n                if valid(x_,y_) and (x_, y_, x, y) not in visited:\n                    q.append((x_, y_, x, y))\n                    visited.add((x_, y_, x, y))\n                    grid[x_][y_] = \\\"b\\\"\n                    # print((x_, y_, x, y))\n                    px, py = x_+x, y_+y\n                    for dx, dy in (-1, 0), (0,-1), (0,1), (1,0):\n                        x2, y2 = x_+dx, y_+dy\n                        # print(x2, y2)\n                        \n                        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:\n                            q.append((x_,y_,x2-x_,y2-y_))\n                            visited.add((x_,y_,x2-x_,y2-y_))\n                            # print((x_,y_,x_-x2,y_-y2))\n                    grid[x_][y_] = \\\".\\\"\n        return -1\n            \n            \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        n, m = len(grid), len(grid[0])\n\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == 'T':\n                    t = (i, j)\n                elif grid[i][j] == 'S':\n                    s = (i, j)\n                elif grid[i][j] == 'B':\n                    b = (i, j)\n        \n        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n        q = [tuple(s + b)]\n        seen = set(q)\n        steps = 0\n        while q:\n            nq = []\n            for si, sj, bi, bj in q:\n                if t == (bi, bj): \n                    return steps\n                for di, dj in dirs:\n                    nsi, nsj = si + di, sj + dj\n                    if nsi == bi and nsj == bj:\n                        nbi, nbj = bi + di, bj + dj\n                        ds = 1\n                    else:\n                        nbi, nbj = bi, bj\n                        ds = 0\n                    if not (0 <= nsi < n and 0 <= nsj < m): \n                        continue\n                    if not (0 <= nbi < n and 0 <= nbj < m): \n                        continue\n                    if grid[nsi][nsj] == '#' or grid[nbi][nbj] == '#': \n                        continue\n                    nsb = (nsi, nsj, nbi, nbj)\n                    if nsb in seen: \n                        continue\n                    seen.add(nsb)\n                    if ds == 0:\n                        q.append(nsb)\n                    else:\n                        nq.append(nsb)\n            q = nq\n            steps += 1\n        return -1\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'\n        dist = lambda i, j: abs(i - ti) + abs(j - tj)\n        \n        m, n = len(grid), len(grid[0])\n        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n        pi, pj, bi, bj = 0, 0, 0, 0\n        ti, tj = 0, 0\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    pi, pj = i, j\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                if grid[i][j] == 'T':\n                    ti, tj = i, j\n        for i, j in [[ti, tj], [bi, bj]]:\n            k = 0\n            for di, dj in dij:\n                ii, jj = i + di, j + dj\n                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':\n                    k += 1\n            if k == 4:\n                return -1\n        q = [(0, pi, pj, bi, bj)]\n        visited = {(pi, pj, bi, bj)}\n        pushes = 1e6\n        while q:\n            psh, pi, pj, bi, bj = heapq.heappop(q)\n            if grid[bi][bj] == 'T':\n                return psh\n            for di, dj in dij:\n                pii, pjj = pi + di, pj + dj\n                if not check(pii, pjj):\n                    continue\n                if pii == bi and pjj == bj:\n                    bii, bjj = bi + di, bj + dj\n                    if not check(bii, bjj):\n                        continue\n                    if grid[bii][bjj] == 'T':\n                        return psh + 1\n                    st = (pii, pjj, bii, bjj)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh + 1, pii, pjj, bii, bjj))\n                else:\n                    st = (pii, pjj, bi, bj)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh, pii, pjj, bi, bj))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        rows, cols = len(grid), len(grid[0])\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == 'T':\n                    target = (r,c)\n                if grid[r][c] == 'S':\n                    start_person = (r,c)\n                if grid[r][c] == 'B':\n                    start_box = (r,c)\n            \n        def heuristic(box):\n            return abs(target[0]-box[0]) + abs(target[1]-box[1])\n\n        def out_bounds(location):\n            r,c=location\n            return r<0 or r>=rows or c<0 or c>=cols or grid[r][c] == '#'\n\n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        vis = set([start_person,start_box])\n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n\n            for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:\n                new_person = (person[0]+dr,person[1]+dc)\n                if out_bounds(new_person):\n                    continue\n\n                if new_person == box:\n                    new_box = (box[0]+dr, box[1]+dc)\n                    if out_bounds(new_box) or (new_person, new_box) in vis:\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box)+moves+1, moves+1, new_person, new_box])\n                    vis.add((new_person, new_box))\n                else:\n                    if (new_person, box) in vis:\n                        continue\n                    heapq.heappush(heap, [heuristic(box)+moves, moves, new_person, box])\n                    vis.add((new_person, box))\n\n        return -1\n                        \n                    \n                    \n                    \n                    \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'\n        dist = lambda i, j: abs(i - ti) + abs(j - tj)\n        \n        m, n = len(grid), len(grid[0])\n        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n        pi, pj, bi, bj = 0, 0, 0, 0\n        ti, tj = 0, 0\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    pi, pj = i, j\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                if grid[i][j] == 'T':\n                    ti, tj = i, j\n        for i, j in [[ti, tj], [bi, bj]]:\n            k = 0\n            for di, dj in dij:\n                ii, jj = i + di, j + dj\n                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':\n                    k += 1\n            if k == 4:\n                return -1\n        q = [(0, pi * n + pj, bi * n + bj)]\n        visited = {(pi * n + pj, bi * n + bj)}\n        pushes = 1e6\n        while q:\n            psh, p, b = heapq.heappop(q)\n            pi, pj = divmod(p, n)\n            bi, bj = divmod(b, n)\n            if grid[bi][bj] == 'T':\n                return psh\n            for di, dj in dij:\n                pii, pjj = pi + di, pj + dj\n                if not check(pii, pjj):\n                    continue\n                if pii == bi and pjj == bj:\n                    bii, bjj = bi + di, bj + dj\n                    if not check(bii, bjj):\n                        continue\n                    if grid[bii][bjj] == 'T':\n                        return psh + 1\n                    st = (pii * n + pjj, bii * n + bjj)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh + 1, pii * n + pjj, bii * n + bjj))\n                else:\n                    st = (pii * n + pjj, b)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh, pii * n + pjj, b))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')\n        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')\n        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')\n        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')\n        heap = [(0, si, sj, boxi, boxj)]\n        def add(moves, *state, added=set()):\n            if state not in added:\n                heapq.heappush(heap, (moves, *state))\n                added.add(state)\n        while heap:\n            moves, si, sj, boxi, boxj = heapq.heappop(heap)\n            if (boxi, boxj) == target:\n                return moves\n            for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):\n                ni, nj = si + dx, dy + sj\n                if (ni, nj) == (boxi, boxj):\n                    if (boxi + dx, boxj + dy) in free:\n                        add(moves + 1, ni, nj, boxi + dx, boxj + dy)\n                elif (ni, nj) in free:\n                    add(moves, ni, nj, boxi, boxj)\n        return -1\n", "import heapq\n\nclass Solution:\n  def minPushBox(self, grid: List[List[str]]) -> int:\n    # bfs, dfs, a-star search\n    # key:\n    # represent the state using (xb, yb, xp, yp), box and storekeeper coordinates, where storekeeper can move around,\n    # up down left and right, and push the box when storekeeper move to box position and the cell next to it is empty.\n    m, n = len(grid), len(grid[0])\n    xb, yb, xs, ys, xt, yt = -1, -1, -1, -1, -1, -1\n    for x in range(m):\n      for y in range(n):\n        if grid[x][y] == 'B':\n          xb, yb = x, y\n          grid[x][y] = '.'\n        if grid[x][y] == 'S':\n          xs, ys = x, y\n          grid[x][y] = '.'\n        if grid[x][y] == 'T':\n          xt, yt = x, y\n          grid[x][y] = '.'\n    # a-star search\n    # heuristic: h(box, target) = abs(xb - xt) + abs(yb - yt), as the lower bound of moves to push box to target.\n    \n    # init\n    q, seen = [(abs(xb - xt) + abs(yb - yt) + 0, 0, xb, yb, xs, ys)], set()\n    while q:\n      h, d, xb, yb, xs, ys = heapq.heappop(q)\n      if (xb, yb) == (xt, yt):\n        return d\n      if (xb, yb, xs, ys) not in seen:\n        seen.add((xb, yb, xs, ys))\n        # storekeeper moves around and pushes the box when step into box coordinates\n        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n          xr, yr = xs + dx, ys + dy\n          if 0 <= xr < m and 0 <= yr < n and grid[xr][yr] == '.':\n            if (xr, yr) == (xb, yb):\n              xc, yc = xb + dx, yb + dy\n              if 0 <= xc < m and 0 <= yc < n and grid[xc][yc] == '.':\n                heapq.heappush(q, (abs(xc - xt) + abs(yc - yt) + d + 1, d + 1, xc, yc, xr, yr))\n            else:\n              heapq.heappush(q, (h, d, xb, yb, xr, yr))\n    return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')\n        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')\n        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')\n        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')\n        visited = set()\n        heap = [(0, si, sj, boxi, boxj)]\n        while heap:\n            moves, si, sj, boxi, boxj = heapq.heappop(heap)\n            if (boxi, boxj) == target:\n                return moves\n            if (si, sj, boxi, boxj) in visited:\n                continue\n            visited.add((si, sj, boxi, boxj))\n            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                ni, nj = si + dx, dy + sj\n                if (ni, nj) == (boxi, boxj) and (boxi + dx, boxj + dy) in free and (ni, nj, boxi + dx, boxj + dy) not in visited:\n                    heapq.heappush(heap, (moves + 1, ni, nj, boxi + dx, boxj + dy))\n                elif (ni, nj) in free and (ni, nj) != (boxi, boxj) and (ni, nj, boxi, boxj) not in visited:\n                    heapq.heappush(heap, (moves, ni, nj, boxi, boxj))\n        return -1         ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        M, N = len(grid), len(grid[0])\n        for i in range(M):\n            for j in range(N):\n                if grid[i][j] in ['#', '.']:\n                    continue\n                if grid[i][j] == 'S':\n                    player = (i, j)\n                elif grid[i][j] == 'B':\n                    box = (i, j)\n                else:\n                    target = (i, j)\n        \n        @lru_cache(None)\n        def reach(player, pos, box):\n            i, j = pos\n            if not (0 <= i < M and 0 <= j < N and grid[i][j] != '#'):\n                return False\n            hp = [player]\n            seen = set([player])\n            while hp:\n                player = heapq.heappop(hp)\n                if player == pos:\n                    return True\n                p0, p1 = player\n                for i, j in [(p0 - 1, p1), (p0 + 1, p1), (p0, p1 - 1), (p0, p1 + 1)]:\n                    if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and (i, j) != box and (i, j) not in seen:\n                        seen.add((i, j))\n                        heapq.heappush(hp, (i, j))\n            return False\n        \n        seen = set([(box, player)])\n        hp = [(0, box, player)]\n        while hp:\n            step, box, player = heapq.heappop(hp)\n            # print(box)\n            if box == target:\n                return step\n            b0, b1 = box\n            for i, j in [(b0 - 1, b1), (b0 + 1, b1), (b0, b1 - 1), (b0, b1 + 1)]:\n                if 0 <= i < M and 0 <= j < N and grid[i][j] != '#' and ((i, j), player) not in seen and reach(player, (\n                b0 * 2 - i, b1 * 2 - j), box):\n                    seen.add(((i, j), player))\n                    heapq.heappush(hp, (step + 1, (i, j), box))\n        return -1\n                    \n                \n                \n                \n                \n                \n                \n                \n                \n                \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        qq = collections.deque()\n        xx = [1,2,3]\n        yy = [4,5,6]\n        qq.appendleft([7,8,9])\n        qq.appendleft(yy)\n        print(len(qq))\n        \n        px,py,bx,by,tx,ty = 0,0,0,0,0,0\n        visited = {}\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"B\\\":\n                    bx = i\n                    by = j\n                    grid[i][j] = \\\".\\\"\n                elif grid[i][j] == \\\"T\\\":\n                    tx = i\n                    ty = j\n                    grid[i][j] = \\\".\\\"\n                elif grid[i][j] == \\\"S\\\":\n                    px = i\n                    py = j\n                    \n                    grid[i][j] = \\\".\\\"\n                \n        \n        dir0 = [[0,1],[0,-1],[1,0],[-1,0]]\n        visited[(bx,by,px,py)] = 0\n        #q = [[bx,by,px,py]]\n        q = collections.deque()\n        q.append([bx,by,px,py])\n        step = 0\n        while q:\n            #co  = q.pop(0)\n            co  = q.popleft()\n            if co[0]==tx and co[1]==ty:\n                return visited[(co[0],co[1],co[2],co[3])]\n            \n            for y in range(len(dir0)):\n                newx = co[2] + dir0[y][0]\n                newy = co[3] + dir0[y][1]\n                if newx<0 or newx>= m or newy<0 or newy>=n or (co[0],co[1],newx,newy) in visited:\n                    continue\n                if newx==co[0] and newy==co[1]:\n                    continue\n                if grid[newx][newy]!=\\\".\\\":\n                    continue\n                #q.insert(0,[co[0],co[1],newx,newy])\n                q.appendleft([co[0],co[1],newx,newy])\n                step = visited.get((co[0],co[1],co[2],co[3]),0)\n                visited[(co[0],co[1],newx,newy)] = step\n                \n            \n            if abs(co[0]-co[2]) + abs(co[1]-co[3]) == 1:\n                for y in range(len(dir0)):\n                    if co[2]+dir0[y][0]==co[0] and co[3] + dir0[y][1] == co[1]:\n                        newx = co[0] + dir0[y][0]\n                        newy = co[1] + dir0[y][1]\n                        if newx<0 or newx>= m or newy<0 or newy>=n or (newx,newy,co[0],co[1]) in visited:\n                            continue\n                        if grid[newx][newy]!=\\\".\\\":\n                            continue                \n                        q.append([newx,newy,co[0],co[1]])\n                        step = visited.get((co[0],co[1],co[2],co[3]),0)\n                        visited[(newx,newy,co[0],co[1])] = step+1\n        return -1       \n            \n            \n            \n            \n            \n            ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        free = set()\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'T':\n                    tx, ty = i, j\n                    free.add((i, j))\n                if grid[i][j] == 'S':\n                    sx, sy = i, j\n                    free.add((i, j))\n                if grid[i][j] == 'B':\n                    bx, by = i, j\n                    free.add((i, j))\n                if grid[i][j] == '.':\n                    free.add((i, j))\n        pq = [(0, sx, sy, bx, by)]\n        visited = set()\n        direction = [(0,1), (1,0), (-1,0), (0,-1)]\n        while pq:\n            moves, sx, sy, bx, by = heapq.heappop(pq)\n            if bx == tx and by == ty:\n                return moves\n            if (sx, sy, bx, by) in visited:\n                continue\n            visited.add((sx, sy, bx, by))\n            for d in direction:\n                dx, dy = d\n                if sx + dx == bx and sy + dy == by and (bx + dx, by + dy) in free:\n                    heapq.heappush(pq, (moves + 1, sx + dx, sy + dy, bx + dx, by + dy))\n                if (sx + dx, sy + dy) in free and (sx + dx, sy + dy) != (bx, by) and (sx + dx, sy + dy, bx, by) not in visited:\n                    heapq.heappush(pq, (moves, sx + dx, sy + dy, bx, by))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        r, c = len(grid), len(grid[0])\n        dire = [[0, 1], [0, -1], [-1, 0], [1, 0]]\n        for i in range(r):\n            for j in range(c):\n                if grid[i][j] == 'T':\n                    T = (i, j)\n                elif grid[i][j] == 'B':\n                    B = (i, j)\n                elif grid[i][j] == 'S':\n                    S = (i, j)\n\n        def check1(x, y):\n            return x >= 0 and x < r and y >= 0 and y < c and grid[x][y] != '#'\n\n        def canMoveTo(e, b, q, vis):\n            while q:\n                pre = q.pop(0)\n                if pre == e:\n                    return True\n\n                for i, j in dire:\n                    nx, ny = pre[0] + i, pre[1] + j\n                    if check1(nx, ny) and \\\\\n                        (nx, ny) != b and (nx, ny) not in vis:\n                        q.append((nx, ny))\n                        vis.add((nx, ny))\n            return False\n\n        def move(e, q, vis):\n            res = 0\n            while q:\n                for _ in range(len(q)):\n                    b, p = q.pop(0)\n                    if b == e:\n                        return res\n                    \n                    for i, j in dire:\n                        nx, ny = b[0] + i, b[1] + j\n                        if check1(nx, ny) and \\\\\n                            check1(b[0] - i, b[1] - j) and\\\\\n                            ((nx, ny), b) not in vis and \\\\\n                            canMoveTo((b[0] - i, b[1] - j), b, [p], set([p])):\n                            q.append(((nx, ny), b))\n                            vis.add(((nx, ny), b))\n                res += 1\n            return -1\n\n        return move(T, [(B, S)], set([(B, S)]))", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'S':\n                    si, sj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    ti, tj = i, j\n                    grid[i][j] = '.'\n        q = [(bi, bj, si, sj, 0)]\n        seen = {(bi, bj, si, sj)}\n        while q:\n            bi, bj, si, sj, dist = q.pop(0)\n            if (bi, bj) == (ti, tj):\n                return dist\n            validMoves = self.canMoveTo(grid, bi, bj, si, sj, {(si, sj)})\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                si_new, sj_new = bi+dx, bj+dy\n                bi_new, bj_new = bi-dx, bj-dy\n                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] == '.':\n                    q.append((bi_new, bj_new, bi, bj, dist+1))\n                    seen.add((bi_new, bj_new, bi, bj))\n        return -1\n    \n    def canMoveTo(self, grid, bi, bj, si, sj, validSet):\n        m, n = len(grid), len(grid[0])\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            if (i, j) in validSet:\n                continue\n            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                validSet.add((i, j))\n                self.canMoveTo(grid, bi, bj, i, j, validSet)\n        return validSet\n    \n    '''\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            if si == si_new and sj == sj_new:\n                return True\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return False\n\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):\n        m, n = len(grid), len(grid[0])\n        if si == si_new and sj == sj_new:\n            return True\n        visited.add((si, sj))\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            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):\n                return True\n        return False\n    '''    ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        self.empty = [['.' for _ in range(n)] for _ in range(m)]\n        for i, row in enumerate(grid):\n            for j, c in enumerate(row):\n                if c == 'B': start = (i,j)\n                if c == 'S': player = (i,j)\n                if c == 'T': target = (i,j)\n                if c == '#': self.empty[i][j] = '#'\n        visit = [[0 for _ in range(n)] for _ in range(m)]\n        visit[start[0]][start[1]] += 1\n        deq = collections.deque([(start,player,(-1,-1))])\n        push = 0\n        while deq and push < m * n:\n            sz = len(deq)\n            for i in range(sz):\n                box,player, previous = deq.popleft()\n                if box == target: return push\n                cango = self.player(player, box,self.empty)\n                for d in self.direction:\n                    nr, nc = box[0] + d[0], box[1] + d[1]\n                    pr,pc = box[0] + d[2], box[1] + d[3]\n                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:\n                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:\n                            visit[nr][nc] +=1\n                            deq.append(((nr,nc),(pr,pc),box))\n            push += 1\n        return -1\n    \n    def player(self, player, box, grid):\n        m, n = len(grid), len(grid[0])\n        visit = [[False for _ in range(n)] for _ in range(m)]\n        visit[player[0]][player[1]] = True\n        deq = collections.deque([player])\n        while deq:\n            sz = len(deq)\n            for i in range(sz):\n                cur = deq.popleft()\n                for d in self.direction:\n                    nr, nc = cur[0] + d[0], cur[1] + d[1]\n                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):\n                        visit[nr][nc] = True\n                        deq.append((nr,nc))\n        return visit\n    \n    def __init__(self):\n        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))\n        self.empty = None", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        free = set((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell != '#')\n        target = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'T')\n        boxi, boxj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'B')\n        si, sj = next((i, j) for i, row in enumerate(grid) for j, cell in enumerate(row) if cell == 'S')\n        visited = set()\n        heap = [(0, si, sj, boxi, boxj)]\n        while heap:\n            moves, si, sj, boxi, boxj = heapq.heappop(heap)\n            if (boxi, boxj) == target:\n                return moves\n            if (si, sj, boxi, boxj) in visited:\n                continue\n            visited.add((si, sj, boxi, boxj))\n            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                ni, nj = si + dx, dy + sj\n                if (ni, nj) == (boxi, boxj) and (boxi + dx, boxj + dy) in free and (ni, nj, boxi + dx, boxj + dy) not in visited:\n                    heapq.heappush(heap, (moves + 1, ni, nj, boxi + dx, boxj + dy))\n                elif (ni, nj) in free and (ni, nj) != (boxi, boxj) and (ni, nj, boxi, boxj) not in visited:\n                    heapq.heappush(heap, (moves, ni, nj, boxi, boxj))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'S':\n                    si, sj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    ti, tj = i, j\n                    grid[i][j] = '.'\n        q = [(bi, bj, si, sj, 0)]\n        seen = {(bi, bj, si, sj)}\n        while q:\n            bi, bj, si, sj, dist = q.pop(0)\n            if (bi, bj) == (ti, tj):\n                return dist\n            validSet = self.canMoveTo(grid, bi, bj, si, sj)\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                si_new, sj_new = bi+dx, bj+dy\n                bi_new, bj_new = bi-dx, bj-dy\n                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] == '.':\n                    q.append((bi_new, bj_new, bi, bj, dist+1))\n                    seen.add((bi_new, bj_new, bi, bj))\n        return -1\n    \n    def canMoveTo(self, grid, bi, bj, si, sj):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return visited\n    \n    '''\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            if si == si_new and sj == sj_new:\n                return True\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return False\n        \n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):\n        m, n = len(grid), len(grid[0])\n        if si == si_new and sj == sj_new:\n            return True\n        visited.add((si, sj))\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            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):\n                return True\n        return False\n        \n    def canMoveTo(self, grid, bi, bj, si, sj, validSet):\n        m, n = len(grid), len(grid[0])\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            if (i, j) in validSet:\n                continue\n            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                validSet.add((i, j))\n                self.canMoveTo(grid, bi, bj, i, j, validSet)\n        return validSet\n    '''    ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'S':\n                    si, sj = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    ti, tj = i, j\n                    grid[i][j] = '.'\n        q = [(bi, bj, si, sj, 0)]\n        seen = {(bi, bj, si, sj)}\n        while q:\n            bi, bj, si, sj, dist = q.pop(0)\n            if (bi, bj) == (ti, tj):\n                return dist\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                si_new, sj_new = bi+dx, bj+dy\n                bi_new, bj_new = bi-dx, bj-dy\n                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] == '.':\n                    q.append((bi_new, bj_new, bi, bj, dist+1))\n                    seen.add((bi_new, bj_new, bi, bj))\n        return -1\n    \n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new, visited):\n        m, n = len(grid), len(grid[0])\n        if si == si_new and sj == sj_new:\n            return True\n        visited.add((si, sj))\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            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):\n                return True\n        return False\n    '''\n    def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):\n        m, n = len(grid), len(grid[0])\n        q = [(si, sj)]\n        visited = {(si, sj)}\n        while q:\n            si, sj = q.pop(0)\n            if si == si_new and sj == sj_new:\n                return True\n            for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n                i, j = si+dx, sj+dy\n                if (i, j) not in visited and 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                    q.append((i, j))\n                    visited.add((i, j))\n        return False\n\n\n        \n    def canMoveTo(self, grid, bi, bj, si, sj, validSet):\n        m, n = len(grid), len(grid[0])\n        for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n            i, j = si+dx, sj+dy\n            if (i, j) in validSet:\n                continue\n            if 0 <= i < m and 0 <= j < n and (i, j) != (bi, bj) and grid[i][j] != '#':\n                validSet.add((i, j))\n                self.canMoveTo(grid, bi, bj, i, j, validSet)\n        return validSet\n    '''    ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        check = lambda i, j: 0 <= i < m and 0 <= j < n and grid[i][j] != '#'\n        \n        m, n = len(grid), len(grid[0])\n        dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n        pi, pj, bi, bj = 0, 0, 0, 0\n        ti, tj = 0, 0\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    pi, pj = i, j\n                if grid[i][j] == 'B':\n                    bi, bj = i, j\n                if grid[i][j] == 'T':\n                    ti, tj = i, j\n        for i, j in [[ti, tj], [bi, bj]]:\n            k = 0\n            for di, dj in dij:\n                ii, jj = i + di, j + dj\n                if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':\n                    k += 1\n            if k == 4:\n                return -1\n        q = [(0, pi, pj, bi, bj)]\n        visited = {(pi, pj, bi, bj)}\n        pushes = 1e6\n        while q:\n            psh, pi, pj, bi, bj = heapq.heappop(q)\n            if grid[bi][bj] == 'T':\n                pushes = min(pushes, psh)\n                continue\n            for di, dj in dij:\n                pii, pjj = pi + di, pj + dj\n                if not check(pii, pjj):\n                    continue\n                if pii == bi and pjj == bj:\n                    bii, bjj = bi + di, bj + dj\n                    if not check(bii, bjj):\n                        continue\n                    st = (pii, pjj, bii, bjj)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh + 1, pii, pjj, bii, bjj))\n                else:\n                    st = (pii, pjj, bi, bj)\n                    if st not in visited:\n                        visited.add(st)\n                        heapq.heappush(q, (psh, pii, pjj, bi, bj))\n        return pushes if pushes < 1e6 else -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        self.empty = [['.' for _ in range(n)] for _ in range(m)]\n        for i, row in enumerate(grid):\n            for j, c in enumerate(row):\n                if c == 'B': start = (i,j)\n                if c == 'S': player = (i,j)\n                if c == 'T': target = (i,j)\n                if c == '#': self.empty[i][j] = '#'\n        visit = [[0 for _ in range(n)] for _ in range(m)]\n        visit[start[0]][start[1]] += 1\n        deq = collections.deque([(start,player,(-1,-1))])\n        push = 0\n        while deq and push < m * n:\n            sz = len(deq)\n            for i in range(sz):\n                box,player, previous = deq.popleft()\n                if box == target: return push\n                cango = self.player(player, box,self.empty)\n                for d in self.direction:\n                    nr, nc = box[0] + d[0], box[1] + d[1]\n                    pr,pc = box[0] + d[2], box[1] + d[3]\n                    if 0<=nr < m and 0<=nc < n and 0<=pr < m and 0<=pc < n:\n                        if (self.empty[nr][nc] == '.') and cango[pr][pc] and visit[nr][nc] < 2:\n                            visit[nr][nc] +=1\n                            deq.append(((nr,nc),(pr,pc),box))\n            push += 1\n        return -1\n    \n    def player(self, player, box, grid):\n        m, n = len(grid), len(grid[0])\n        visit = [[False for _ in range(n)] for _ in range(m)]\n        togo = [[False for _ in range(n)] for _ in range(m)]\n        visit[player[0]][player[1]], togo[player[0]][player[1]] = True, True\n        deq = collections.deque([player])\n        while deq:\n            sz = len(deq)\n            for i in range(sz):\n                cur = deq.popleft()\n                for d in self.direction:\n                    nr, nc = cur[0] + d[0], cur[1] + d[1]\n                    if 0<=nr < m and 0<=nc < n and grid[nr][nc] == '.' and not visit[nr][nc] and box != (nr,nc):\n                        visit[nr][nc] = True\n                        togo[nr][nc] = True\n                        deq.append((nr,nc))\n        return visit\n    \n    def __init__(self):\n        self.direction = ((0,1,0,-1),(0,-1,0,1),(1,0,-1,0),(-1,0,1,0))\n        self.empty = None", "class Solution:\n    FLOOR = \\\".\\\"\n    WALL = \\\"#\\\"\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        player, box, target = (0, 0), (0, 0), (0, 0)\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"S\\\": player = (i, j)\n                if grid[i][j] == \\\"B\\\": box = (i, j)\n                if grid[i][j] == \\\"T\\\": target = (i, j)\n        \n        hq = [(abs(target[0] - box[0]) + abs(target[1] - box[1]), 0, box, player)]\n        steps = collections.defaultdict(int)\n        \n        while len(hq) > 0:\n            curr_heuristic_est, curr_steps, (curr_i, curr_j), player = heappop(hq)\n            if (curr_i, curr_j) == target:\n                return curr_steps\n            \n            for next_i, next_j in self._get_next(grid, curr_i, curr_j, player):\n                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))]:\n                    player = (curr_i, curr_j)\n                    steps[((next_i, next_j), (curr_i, curr_j))] = curr_steps + 1\n                    heappush(hq, (curr_steps + 1 + abs(target[0]-next_i) + abs(target[1]-next_j), curr_steps + 1, (next_i, next_j), player))\n                    \n        return -1\n                   \n        \n    def _get_next(self, grid, curr_i, curr_j, player):\n        \\\"\\\"\\\"\n        Return a list of posible positions the box could be moved to. There are basically 4 choices\n        \\\"\\\"\\\"\n        m, n = len(grid), len(grid[0])\n        res = []\n        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()):\n            res.append((curr_i - 1, curr_j))\n        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()):\n            res.append((curr_i + 1, curr_j))\n        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()):\n            res.append((curr_i, curr_j - 1))\n        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()):\n            res.append((curr_i, curr_j + 1))\n        return res\n    \n    \n    def _can_player_reach(self, grid, curr_pos, dst, box, visited):\n        \\\"\\\"\\\"\n        Return if player can reach dst position by doing bfs/dfs\n        \\\"\\\"\\\"\n        m, n = len(grid), len(grid[0])\n        if curr_pos[0] < 0 or curr_pos[0] >= m or curr_pos[1] < 0 or curr_pos[1] >= n:\n            return False\n        if curr_pos == dst:\n            return True\n        \n        for delta_i, delta_j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:\n            next_i, next_j = curr_pos[0] + delta_i, curr_pos[1] + delta_j\n            if 0 <= next_i < m and 0 <= next_j < n:\n                if grid[next_i][next_j] != self.WALL:\n                    if (next_i, next_j) not in visited and (next_i, next_j) != box:\n                        visited.add((next_i, next_j))\n                        if self._can_player_reach(grid, (next_i, next_j), dst, box, visited):\n                            return True\n        return False", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m,n=len(grid),len(grid[0])\n        dirs=[(0,1),(0,-1),(1,0),(-1,0)]\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]=='S':\n                    S=(i,j)\n                if grid[i][j]=='B':\n                    B=(i,j)\n                if grid[i][j]=='T':\n                    T=(i,j)\n                    \n                    \n        def check(x,y):    #\u5224\u65ad\u8fd9\u4e2a\u4f4d\u7f6e\u662f\u5426\u6709\u6548\n            return 0<=x<m and 0<=y<n and grid[x][y]!='#'\n                    \n            \n        def canmoveto(e,b,q,visit):          #\u5224\u65ad\u4eba\u80fd\u5426\u5230\u8fbe\u76ee\u6807\u4f4d\u7f6e\n            while q:\n                p=q.pop(0)\n                if p==e:\n                    return True\n                for dx,dy in dirs:\n                    nx,ny=p[0]+dx,p[1]+dy\n                    if check(nx,ny) and (nx,ny)!=b and (nx,ny) not in visit:\n                        q.append((nx,ny))\n                        visit.add((nx,ny))\n            return False\n        \n        def move(e,q,visit):   #\u5224\u65ad\u4eba\u80fd\u5426\u628a\u7bb1\u5b50\u63a8\u5230\u76ee\u6807\u4f4d\u7f6e\n            res = 0\n            while q:\n                size=len(q)\n                for _ in range(size):\n                    b, p = q.pop(0)\n                    if b == e:\n                        return res\n                    \n                    for dx,dy in dirs:\n                        nbx, nby = b[0] +dx, b[1] +dy\n                        npx,npy=b[0]-dx,b[1]-dy\n                        if check(nbx, nby) and \\\\\n                            check(npx,npy) and\\\\\n                            ((nbx, nby), b) not in visit and \\\\\n                            canmoveto((npx,npy), b, [p], set([p])):\n                            q.append(((nbx, nby), b))\n                            visit.add(((nbx, nby), b))\n                res += 1\n            return -1\n        return move(T,[(B,S)],set([(B,S)]))\n                        \n                \n                \n        \n        ", "class Solution:\n    FLOOR = \\\".\\\"\n    WALL = \\\"#\\\"\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        player, box, target = (0, 0), (0, 0), (0, 0)\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \\\"S\\\": player = (i, j)\n                if grid[i][j] == \\\"B\\\": box = (i, j)\n                if grid[i][j] == \\\"T\\\": target = (i, j)\n        print(box, target)\n        \n        hq = [(abs(target[0] - box[0]) + abs(target[1] - box[1]), 0, box, player)]\n        steps = collections.defaultdict(int)\n        # steps[box] = 0\n        \n        while len(hq) > 0:\n            curr_heuristic_est, curr_steps, (curr_i, curr_j), player = heappop(hq)\n            print(curr_heuristic_est, curr_steps, (curr_i, curr_j), player)\n            if (curr_i, curr_j) == target:\n                return curr_steps\n            \n            for next_i, next_j in self._get_next(grid, curr_i, curr_j, player):\n                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))]:\n                    player = (curr_i, curr_j)\n                    steps[((next_i, next_j), (curr_i, curr_j))] = curr_steps + 1\n                    heappush(hq, (curr_steps + 1 + abs(target[0]-next_i) + abs(target[1]-next_j), curr_steps + 1, (next_i, next_j), player))\n                    \n        return -1\n                   \n        \n    def _get_next(self, grid, curr_i, curr_j, player):\n        \\\"\\\"\\\"\n        Return a list of posible positions the box could be moved to. There are basically 4 choices\n        \\\"\\\"\\\"\n        m, n = len(grid), len(grid[0])\n        res = []\n        if (curr_i, curr_j) == (2, 1):\n            print(curr_i, curr_j, grid[curr_i - 1][curr_j], player)\n        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()):\n            res.append((curr_i - 1, curr_j))\n        if (curr_i, curr_j) == (2, 1):\n            print(res)\n        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()):\n            res.append((curr_i + 1, curr_j))\n        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()):\n            res.append((curr_i, curr_j - 1))\n        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()):\n            res.append((curr_i, curr_j + 1))\n        return res\n    \n    \n    def _can_player_reach(self, grid, curr_pos, dst, box, visited):\n        \\\"\\\"\\\"\n        Return if player can reach dst position by doing bfs/dfs\n        \\\"\\\"\\\"\n        m, n = len(grid), len(grid[0])\n        if curr_pos[0] < 0 or curr_pos[0] >= m or curr_pos[1] < 0 or curr_pos[1] >= n:\n            return False\n        if dst == (3, 1):\n            print(curr_pos, \\\"ha\\\")\n        if curr_pos == dst:\n            return True\n        \n        for delta_i, delta_j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:\n            next_i, next_j = curr_pos[0] + delta_i, curr_pos[1] + delta_j\n            if 0 <= next_i < m and 0 <= next_j < n:\n                if grid[next_i][next_j] != self.WALL:\n                    if (next_i, next_j) not in visited and (next_i, next_j) != box:\n                        visited.add((next_i, next_j))\n                        if self._can_player_reach(grid, (next_i, next_j), dst, box, visited):\n                            return True\n        return False", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        self.m = len(grid)\n        self.n = len(grid[0])\n        player, box = [0, 0], [0, 0]\n        \n        for i in range(self.m):\n            for j in range(self.n):\n                if grid[i][j] == 'B':\n                    box = [i, j]\n                elif grid[i][j] == 'S':\n                    player = [i, j]\n        \n        i, j = box\n        x, y = player\n        q = collections.deque()\n        q.append((i, j, x, y))  # i, j is where the box is, x, y is where the player is\n        visited = set()\n        visited.add((i, j, x, y))\n        \n        step = 0\n        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n        while q:\n            size = len(q)\n            for _ in range(size):\n                i, j, x, y = q.popleft()\n                if grid[i][j] == 'T':\n                    return step\n                \n                for di, dj in dirs:\n                    i2 = i + di\n                    j2 = j + dj\n                    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):\n                        continue\n                \n                    q.append((i2, j2, i, j))\n                    visited.add((i2, j2, i, j))\n            step += 1\n        \n        return -1\n    \n    def helper(self, grid, x, y, bi, bj, i, j):\n        # check if the player can go from x, y to i, j\n        visited = set()\n        return self.has_path(grid, x, y, bi, bj, i, j, visited)\n    \n    def has_path(self, grid, x, y, bi, bj, i, j, visited):\n        # check if the player can go from x, y to i, j\n        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:\n            return False\n        \n        if x == i and y == j:\n            return True\n        \n        visited.add((x, y))\n        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)\n        \n        \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        rows, cols = len(grid), len(grid[0])\n        player = box = target = None\n        for i in range(rows):\n            for j in range(cols):\n                if grid[i][j] == \\\"B\\\":\n                    box = (i, j)\n                elif grid[i][j] == \\\"S\\\":\n                    player = (i, j)\n                elif grid[i][j] == \\\"T\\\":\n                    target = (i, j)\n        \n        def is_valid(pos):\n            r, c = pos\n            if 0 <= r < rows and 0 <= c < cols:\n                return grid[r][c] != \\\"#\\\"\n            return False\n        \n        def get_distance(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n        \n        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n        heap = [(get_distance(box), 0, player, box)]\n        visited = set()\n        \n        while heap:\n            distance, move, player, box = heapq.heappop(heap)\n            if box == target:\n                return move\n            if (player, box) in visited:\n                continue\n            visited.add((player, box))\n            for d in directions:\n                next_player = (player[0] + d[0], player[1] + d[1])\n                if not is_valid(next_player):\n                    continue\n                if box == next_player:\n                    next_box = (box[0] + d[0], box[1] + d[1])\n                    if not is_valid(next_box):\n                        continue\n                    heapq.heappush(heap, (get_distance(next_box) + move + 1, move + 1, next_player, next_box))\n                else:\n                    heapq.heappush(heap, (distance, move, next_player, box))\n        return -1", "from collections import deque\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        m, n = len(grid), len(grid[0])\n        \n        def Can(i, j):\n            ss.add((i, j))\n            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n                if 0 <= x < m and 0 <= y < n and (x, y) not in ss and grid[x][y] == '.':\n                    Can(x, y)\n        \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    ppl = (i, j)\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'B':\n                    box = (i, j)\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    target = (i, j)\n                    grid[i][j] = '.'\n        \n        visited = set()\n        queue = deque()\n        queue.append((box[0], box[1], 0, ppl[0], ppl[1]))\n        ss = set()\n        \n        while queue:\n            x, y, count, p1, p2 = queue.popleft()\n            if (x, y) == target:\n                return count\n            ss = {(x, y)}\n            Can(p1, p2)\n            \n            if x+1 < m and 0 <= x-1 and grid[x+1][y] == '.' and grid[x-1][y] == '.':\n                if (x-1, y, x, y) not in visited and (x-1, y) in ss:\n                    visited.add((x-1, y, x, y))\n                    queue.append( (x+1, y, count+1, x-1, y) )\n                if (x+1, y, x, y) not in visited and (x+1, y) in ss:\n                    visited.add((x+1, y, x, y))\n                    queue.append( (x-1, y, count+1, x+1, y) )\n            \n            if y+1 < n and 0 <= y-1 and grid[x][y-1] == '.' and grid[x][y+1] == '.':\n                #print(\\\"{}.{}\\\".format(x, y))\n                if (x, y-1, x, y) not in visited and (x, y-1) in ss:\n                    visited.add((x, y-1, x, y))\n                    queue.append( (x, y+1, count+1, x, y-1) )\n                if (x, y+1, x, y) not in visited and (x, y+1) in ss:\n                    visited.add((x, y+1, x, y))\n                    queue.append( (x, y-1, count+1, x, y+1) )\n            \n        return -1\n            \n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dx = [-1, 0, 1, 0]\n        dy = [0, 1, 0, -1]\n        n, m = len(grid), len(grid[0])\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == 'B':\n                    b = (i, j)\n                if grid[i][j] == 'S':\n                    s = (i, j)\n                if grid[i][j] == 'T':\n                    t = (i, j)\n        queue = [(b[0], b[1], s[0], s[1], 0)]\n        dic = {(b[0], b[1], s[0], s[1]):0}\n        res = float('inf')\n        while queue:\n            bx, by, sx, sy, step = queue.pop(0)\n            if dic[(bx, by, sx, sy)] >= res:\n                continue\n            if (bx, by) == t:\n                res = min(res, step)\n                continue\n            for i in range(4):\n                nsx = sx + dx[i]\n                nsy = sy + dy[i]\n                if not 0 <= nsx < n or not 0 <= nsy < m or grid[nsx][nsy] == '#':\n                    continue\n                if nsx == bx and nsy == by:\n                    nbx = bx + dx[i]\n                    nby = by + dy[i]\n                    if (nbx, nby, nsx, nsy) in dic and dic[(nbx, nby, nsx, nsy)] <= step + 1:\n                        continue\n                    dic[(nbx, nby, nsx, nsy)] = step+1\n                    queue.append((nbx, nby, nsx, nsy, step + 1))\n                else:\n                    if (bx, by, nsx, nsy) in dic and dic[(bx, by, nsx, nsy)] <= step:\n                        continue\n                    dic[(bx, by, nsx, nsy)] = step\n                    queue.append((bx, by, nsx, nsy, step))\n        return res if res != float('inf') else -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        n,m = len(grid),len(grid[0])\n        B = T = S = None\n        \n        for i in range(n):\n            for j in range(m):\n                if grid[i][j]=='B': B = (i,j)\n                if grid[i][j]=='T': T = (i,j)\n                if grid[i][j]=='S': S = (i,j)\n                    \n        #cost, B, S\n        heap = [((0,B[0],B[1],S[0],S[1]))]\n        heapq.heapify(heap)\n        # bi,bj,si,sj\n        seen = set()\n        while heap:\n            c,bi,bj,si,sj = heapq.heappop(heap)\n            #print((bi,bj),(si,sj),c)\n            if (bi,bj)==T:\n                return c\n            if (bi,bj,si,sj) in seen:\n                continue\n            seen.add((bi,bj,si,sj))\n            for nsi,nsj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:\n                if 0<=nsi<n and 0<=nsj<m and grid[nsi][nsj]!='#':\n                    if (nsi,nsj)!=(bi,bj) and (bi,bj,nsi,nsj) not in seen:  \n                        heapq.heappush(heap,(c,bi,bj,nsi,nsj))\n                    elif (bi,bj) == (nsi,nsj) :\n                        nbi,nbj = nsi-(si-nsi),nsj-(sj-nsj)\n                        if 0<=nbi<n and 0<=nbj<m and (nbi,nbj,nsi,nsj) not in seen:\n                            heapq.heappush(heap,(c+1,nbi,nbj,nsi,nsj))\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dire = [(1,0),(0,1),(-1,0),(0,-1)]\n\\t\\t\n        def can_get(cur_b,cur_p,tar):\n            seen,cur = set([cur_p]),set([cur_p])\n            while cur:\n                tmp = []\n                for loc in cur:\n                    for x,y in dire:\n                        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:\n                            tmp += [(loc[0]+x,loc[1] +y)]\n                cur = set(tmp)\n                seen |= cur\n                if tar in seen:\n                    return True\n            return False\n\\t\\t\\t\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'B': box = (i,j)\n                if grid[i][j] == 'S': player = (i,j)\n                if grid[i][j] == 'T': target = (i,j)\n\\t\\t\\t\\t\n        seen,cur,res = set([(box,player)]), set([(box,player)]), 0\n        while cur:\n            tmp = []\n            res += 1\n            for b,p in cur:\n                for x,y in dire:\n                    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:\n                        tmp += [((b[0]+x,b[1]+y),b)]\n            cur = set(tmp)\n            seen |= cur\n            for x,y in dire:\n                if (target,(target[0]+x,target[1]+y)) in seen:\n                    return res\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n\n        def can_get(cur_b, cur_p, tar):\n            seen, cur = set([cur_p]), set([cur_p])\n            while cur:\n                tmp = []\n                for loc in cur:\n                    for x, y in dire:\n                        if 0 <= loc[0] + x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and (\n                            loc[0] + x, loc[1] + y) != cur_b and grid[loc[0] + x][loc[1] + y] != '#' and (\n                            loc[0] + x, loc[1] + y) not in seen:\n                            tmp += [(loc[0] + x, loc[1] + y)]\n                cur = set(tmp)\n                seen |= cur\n                if tar in seen:\n                    return True\n            return False\n\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'B': box = (i, j)\n                if grid[i][j] == 'S': player = (i, j)\n                if grid[i][j] == 'T': target = (i, j)\n\n        seen, cur, res = set([(box, player)]), set([(box, player)]), 0\n        while cur:\n            tmp = []\n            res += 1\n            for b, p in cur:\n                for x, y in dire:\n                    if 0 <= b[0] + x < len(grid) and 0 <= b[1] + y < len(grid[0]) and grid[b[0] + x][\n                                b[1] + y] != '#' and can_get(b, p, (b[0] - x, b[1] - y)) and (\n                    (b[0] + x, b[1] + y), b) not in seen:\n                        tmp += [((b[0] + x, b[1] + y), b)]\n            cur = set(tmp)\n            seen |= cur\n            for x, y in dire:\n                if (target, (target[0] + x, target[1] + y)) in seen:\n                    return res\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n                \n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    man = (i, j)\n                elif grid[i][j] == 'B':\n                    box = (i, j)\n                elif grid[i][j] == 'T':\n                    target = (i, j)\n        \n        def validPos(loc):\n            i, j = loc\n            return (m > i >= 0 <= j < n) and grid[i][j] != '#'\n        \n        def heuristic(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n        \n        heap = [(heuristic(box), 0, man, box)]\n        seen = set()\n        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        \n        while heap:\n            _, steps, man, box = heapq.heappop(heap)\n            if box == target:\n                return steps\n            if (man, box) in seen:\n                continue\n            seen.add((man, box))\n            for r, c in dirs:\n                new_man = man[0] + r, man[1] + c\n                if not validPos(new_man):\n                    continue\n                if new_man == box:\n                    new_box = box[0] + r, box[1] + c\n                    if not validPos(new_box):\n                         continue\n                    heapq.heappush(heap, (heuristic(new_box) + steps + 1, steps + 1, new_man, new_box))\n                else:\n                    heapq.heappush(heap, (heuristic(box) + steps, steps, new_man, box))\n                    \n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        n, m = len(grid), len(grid[0])\n        \n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == 'T':\n                    target = (i, j)\n                elif grid[i][j] == 'B':\n                    start_box = (i, j)\n                elif grid[i][j] == 'S':\n                    start_person = (i, j)\n        \n        def heuristic(box):\n            return abs(target[0] - box[0]) + abs(target[1] - box[1])\n        \n        def out_bounds(location):\n            i, j = location\n            if i < 0 or i >= n:\n                return True\n            if j < 0 or j >= m:\n                return True\n            return grid[i][j] == '#'\n        \n        heap = [[heuristic(start_box), 0, start_person, start_box]]\n        visited = set()\n        \n        while heap:\n            _, moves, person, box = heapq.heappop(heap)\n            if box == target:\n                return moves\n            if (person, box) in visited:\n                continue\n            visited.add((person, box))\n            \n            for dx, dy in [[0, 1], [1, 0], [-1, 0], [0, -1]]:\n                new_person = (person[0] + dx, person[1] + dy)\n                if out_bounds(new_person):\n                    continue\n                \n                if new_person == box:\n                    new_box = (box[0] + dx, box[1] + dy)\n                    if out_bounds(new_box):\n                        continue\n                    heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])\n                else:\n                    heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box])\n        \n        return -1\n        \n        \n        \n        \n        \n                    \n", "\\\"\\\"\\\"\nlevel 0: [bx,by,px,py]\n\nlevel 1: [bx-1, by, px-1, py]\n\nlevel 3: \n\n\n\\\"\\\"\\\"\n\n\n\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \n        m, n = len(grid), len(grid[0])        \n        bx, by, px, py = 0, 0, 0, 0\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == 'S':\n                    px, py = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'B':\n                    bx, by = i, j\n                    grid[i][j] = '.'\n                elif grid[i][j] == 'T':\n                    tx, ty = i, j\n                    grid[i][j] = '.'\n                \n        queue = collections.deque()\n        queue.append([bx, by, px, py])\n        memo = collections.defaultdict(lambda : -1)\n        memo[(bx, by, px, py)] = 0\n\n        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n\n        while queue:\n            bx, by, px, py = queue.popleft()\n            if bx == tx and by == ty:\n                return memo[(bx, by, px, py)]\n                             \n            for k in range(4):\n                x = px + directions[k][0]\n                y = py + directions[k][1]\n                if x<0 or x>=m or y<0 or y>=n:\n                    continue\n                if grid[x][y] != '.':\n                    continue\n                if x == bx and y == by:\n                    continue\n                if memo[(bx, by, x, y)] >= 0:\n                    continue\n                memo[(bx, by, x, y)] = memo[(bx, by, px, py)]\n                queue.appendleft([bx, by, x, y])\n            \n            #\u76f8\u90bb\n            if abs(px-bx) + abs(py-by) == 1:\n                for k in range(4):\n                    if px+directions[k][0] == bx and py+directions[k][1] == by:\n                        bx2 = bx+directions[k][0]\n                        by2 = by+directions[k][1]\n                        if bx2<0 or bx2>=m or by2<0 or by2>=n:\n                            continue\n                        if grid[bx2][by2] != '.':\n                            continue\n                        if memo[(bx2, by2, bx, by)] >= 0:\n                            continue\n                        memo[(bx2, by2, bx, by)] = memo[(bx, by, px, py)] + 1\n                        queue.append([bx2, by2, bx, by])\n            \n        return -1\n            \n        \n        \n        \n        \n        ", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dire = [(1,0),(0,1),(-1,0),(0,-1)]\n\\t\\t\n        def can_get(cur_b,cur_p,tar):\n            seen,cur = set([cur_p]),set([cur_p])\n            while cur:\n                tmp = []\n                for loc in cur:\n                    for x,y in dire:\n                        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:\n                            tmp += [(loc[0]+x,loc[1] +y)]\n                cur = set(tmp)\n                seen |= cur\n                if tar in seen:\n                    return True\n            return False\n\\t\\t\\t\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'B': box = (i,j)\n                if grid[i][j] == 'S': player = (i,j)\n                if grid[i][j] == 'T': target = (i,j)\n\\t\\t\\t\\t\n        seen,cur,res = set([(box,player)]), set([(box,player)]), 0\n        while cur:\n            tmp = set()\n            res += 1\n            for b,p in cur:\n                for x,y in dire:\n                    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:\n                        tmp.add(((b[0]+x,b[1]+y),b))\n            cur = set(tmp)\n            seen.update(cur)\n            for x,y in dire:\n                if (target,(target[0]+x,target[1]+y)) in seen:\n                    return res\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dire = [(1,0),(0,1),(-1,0),(0,-1)]\n\\t\\t\n        def can_get(cur_b,cur_p,tar):\n            seen,cur = set([cur_p]),set([cur_p])\n            while cur:\n                tmp = set()\n                for loc in cur:\n                    for x,y in dire:\n                        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:\n                            tmp.add((loc[0]+x,loc[1] +y))\n                cur = tmp\n                seen.update(cur)\n                if tar in seen:\n                    return True\n            return False\n\\t\\t\\t\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 'B': box = (i,j)\n                if grid[i][j] == 'S': player = (i,j)\n                if grid[i][j] == 'T': target = (i,j)\n\\t\\t\\t\\t\n        seen,cur,res = set([(box,player)]), set([(box,player)]), 0\n        while cur:\n            tmp = set()\n            res += 1\n            for b,p in cur:\n                for x,y in dire:\n                    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:\n                        tmp.add(((b[0]+x,b[1]+y),b))\n            cur = tmp\n            seen.update(cur)\n            for x,y in dire:\n                if (target,(target[0]+x,target[1]+y)) in seen:\n                    return res\n        return -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n\n        # this loop is to get the coordinates of target, box and person. Nothing else is gained here\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == \\\"T\\\":\n                    target = (i,j)\n                if grid[i][j] == \\\"B\\\":\n                    box = (i,j)\n                if grid[i][j] == \\\"S\\\":\n                    person = (i,j)\n\n        # this function checks whether the given coordinates/indices are valid to go\n        def valid(x,y):\n            return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!='#'\n\n        # this function checks whether the person can travel from current postition to destination position.\n        # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.\n        def check(curr,dest,box):\n            que = deque([curr])\n            v = set()\n            while que:\n                pos = que.popleft()\n                if pos == dest: return True\n                new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]\n                for x,y in new_pos:\n                    if valid(x,y) and (x,y) not in v and (x,y)!=box:\n                        v.add((x,y))\n                        que.append((x,y))\n            return False\n\n        q = deque([(0,box,person)])\n        vis = {box+person}\n        # this is the main bfs which gives us the answer\n        while q :\n            dist, box, person = q.popleft()\n            if box == target: # return the distance if box is at the target\n                return dist\n\n            #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n            b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n            #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n            p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n\n            for new_box,new_person in zip(b_coord,p_coord): \n                # we check if the new box coordinates are valid and our current state is not in vis\n                if valid(*new_box) and new_box+box not in vis:\n                    # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates\n                    if valid(*new_person) and check(person,new_person,box):\n                        vis.add(new_box+box)\n                        q.append((dist+1,new_box,box))\n\n        return -1\n", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        #BFS. \u7ec8\u6b62\u6761\u4ef6\u4e3a\u7bb1\u5b50\u5230\u8fbe\u76ee\u6807\u70b9\uff0c\u6216\u8005\u8fd9\u6761\u8def\u8d70\u8fc7\u4e14\u6709\u66f4\u77ed\u7684\u8d70\u6cd5.\n        n = len(grid)\n        m = len(grid[0])\n        \n        player = None\n        box = None\n        dest = None\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == \\\"B\\\":\n                    box = (i,j)\n                    grid[i][j] = \\\".\\\"\n                elif grid[i][j] == \\\"S\\\":\n                    player = (i,j)\n                    grid[i][j] = \\\".\\\"\n                elif grid[i][j] == \\\"T\\\":\n                    dest = (i, j)\n                    grid[i][j] = \\\".\\\"\n                if player != None and box != None and dest != None:\n                    break\n                    \n        def can_move(r, c, n, m, d, br, bc, cost):\n            if r < 0 or r >= n or c < 0 or c >= m or grid[r][c] == '#':\n                return False\n            if (br,bc) == (r,c):\n                nbr, nbc = r+d[0], c+d[1]\n                br, bc = nbr, nbc\n                if nbr < 0 or nbr >= n or nbc < 0 or nbc >= m or grid[nbr][nbc] == '#':\n                    return False\n                cost += 1\n            if visited[(r,c,br,bc)] <= cost:\n                return False\n                \n            return (br,bc, cost)\n        \n        visited = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        q = [(player[0], player[1], box[0], box[1],0)]\n        res = float(\\\"inf\\\")\n        while len(q)>0:\n            next_q = []\n            for r,c, br, bc, cost in q:\n                # print(r,c, br, bc, cost, pushes)\n                #\u770b\u770b\u56db\u4e2a\u65b9\u5411\u80fd\u4e0d\u80fd\u79fb\u52a8, \u6709\u6ca1\u6709\u7bb1\u5b50\uff0c\u6709\u6ca1\u6709\u5899\uff0c\u662f\u5426\u8d70\u8fc7\n                dir = [(-1,0),(1,0),(0,1),(0,-1)]\n                for d in dir:\n                    # print(\\\"d\\\", d)\n                    nr, nc = r+d[0], c+d[1]\n                    move_res = can_move(nr, nc, n, m, d, br, bc, cost)\n                    if move_res != False:\n                        nbr, nbc, new_cost = move_res\n                        visited[(nr,nc,br,bc)] = new_cost\n                        #\u5224\u65ad\u662f\u5426\u5230\u8fbe\u76ee\u7684\u5730\n                        if (nbr,nbc) == dest:\n                            res = min(res, new_cost)\n                        else:\n                            #\u6ca1\u6709\u5230\u8fbe\u76ee\u6807\u624d\u9700\u8981\u7ee7\u7eed\u904d\u5386\n                            if (nbr,nbc) == (br,bc):\n                                next_q.append((nr,nc,nbr,nbc,new_cost))\n                            else:\n                                next_q.append((nr,nc,nbr,nbc,new_cost))\n                    else:\n                        # print(\\\"False\\\", nr,nc, br, bc, cost)\n                        pass\n                            \n            q = next_q\n            \n        # print(visited)\n        return res if res != float(\\\"inf\\\") else -1", "class Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n        R, C = len(grid), len(grid[0])\n        b_pos = s_pos = t_pos = None\n        for r in range(R):\n            for c in range(C):\n                if grid[r][c] == 'B':\n                    b_pos = (r, c)\n                if grid[r][c] == 'S':\n                    s_pos = (r, c)\n                if grid[r][c] == 'T':\n                    t_pos = (r, c)\n        def is_empty(r, c):\n            return 0 <= r < R and 0 <= c < C and grid[r][c] != '#'\n\n        visited = set()\n        queue = [tuple(b_pos + s_pos)]\n        steps = 0\n        while queue:\n            new_queue = []\n            for br, bc, sr, sc in queue:\n                new = (br, bc, sr, sc)\n                if new in visited:\n                    continue\n                visited.add(new)\n                if (br, bc) == t_pos:\n                    return steps\n                for dr, dc in dirs:\n                    nsr, nsc = dr + sr, dc + sc\n                    if (nsr, nsc) == (br, bc):\n                        nbr, nbc = dr + br, dc + bc\n                        box_move = True\n                    else:\n                        nbr, nbc = br, bc\n                        box_move = False\n                    if not is_empty(nsr, nsc) or not is_empty(nbr, nbc):\n                        continue\n                    new = (nbr, nbc, nsr, nsc)\n                    if box_move:\n                        new_queue.append(new)\n                    else:\n                        queue.append(new)\n            queue = new_queue\n            steps += 1\n        return -1", "import heapq\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j]=='S':\n                    s=(i,j)\n                if grid[i][j]=='B':\n                    b=(i,j)\n                if grid[i][j]=='T':\n                    t=(i,j)\n        def valid(i,j,s=None,b=None):\n            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):\n                return False\n            if grid[i][j]=='#':\n                return False\n            if s is not None:\n                if (i,j)==s:\n                    return False\n            if b is not None:\n                if (i,j)==b:\n                    return False\n            return True\n        def next_state(s,b,step):\n            for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:\n                if valid(s[0]+di,s[1]+dj):\n                    if b==(s[0]+di,s[1]+dj) and valid(b[0]+di,b[1]+dj):\n                        nxt_s,nxt_b,nxt_step=b,(b[0]+di,b[1]+dj),step+1\n                    else:\n                        nxt_s=(s[0]+di,s[1]+dj)\n                        nxt_b,nxt_step=b,step\n                    yield nxt_s,nxt_b,nxt_step\n        def edit_dis(s,b):\n            return abs(s[0]-b[0])+abs(s[1]-b[1])\n        def search(s,b):\n            q=[(0,edit_dis(s,b),s,b)]\n            visited={}\n            visited[(s,b)]=0\n            while q:\n                (step,_,s,b)=heapq.heappop(q)\n                if b==t:\n                    return step\n                for nxt_s,nxt_b,nxt_step in next_state(s,b,step):\n                    if (nxt_s,nxt_b) not in visited or visited[(nxt_s,nxt_b)]>nxt_step:\n                        q.append((nxt_step,edit_dis(nxt_s,nxt_b),nxt_s,nxt_b))\n                        visited[(nxt_s,nxt_b)]=nxt_step\n            return -1\n        return search(s,b)\n                        \n", "import heapq\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j]=='S':\n                    s=(i,j)\n                if grid[i][j]=='B':\n                    b=(i,j)\n                if grid[i][j]=='T':\n                    t=(i,j)\n        def valid(i,j,s=None,b=None):\n            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]):\n                return False\n            if grid[i][j]=='#':\n                return False\n            if s is not None:\n                if (i,j)==s:\n                    return False\n            if b is not None:\n                if (i,j)==b:\n                    return False\n            return True\n        def next_state(s,b,step):\n            for di,dj in [(0,1),(1,0),(0,-1),(-1,0)]:\n                if valid(s[0]+di,s[1]+dj):\n                    if b==(s[0]+di,s[1]+dj) and valid(b[0]+di,b[1]+dj):\n                        nxt_s,nxt_b,nxt_step=b,(b[0]+di,b[1]+dj),step+1\n                    else:\n                        nxt_s=(s[0]+di,s[1]+dj)\n                        nxt_b,nxt_step=b,step\n                    yield nxt_s,nxt_b,nxt_step\n        def edit_dis(s,b):\n            return abs(s[0]-b[0])+abs(s[1]-b[1])\n        def search(s,b):\n            q=[(0,s,b)]\n            visited={}\n            visited[(s,b)]=0\n            while q:\n                (step,s,b)=heapq.heappop(q)\n                if b==t:\n                    return step\n                for nxt_s,nxt_b,nxt_step in next_state(s,b,step):\n                    if (nxt_s,nxt_b) not in visited or visited[(nxt_s,nxt_b)]>nxt_step:\n                        q.append((nxt_step,nxt_s,nxt_b))\n                        visited[(nxt_s,nxt_b)]=nxt_step\n            return -1\n        return search(s,b)\n                        \n", "class Solution:\n    def init_positions(self):\n        for i in range(self.m):\n            for j in range(self.n):\n                if self.grid[i][j] == 'S':\n                    pusher = i, j\n                if self.grid[i][j] == 'B':\n                    box = i, j\n                if self.grid[i][j] == 'T':\n                    target = i, j\n        return pusher, box, target\n        \n    def bfs_from_pusher(self, pusher, box):\n        visited = set()\n        frontier = {pusher}\n        while frontier:\n            visited |= frontier\n            new_frontier = set()\n            for pos in frontier:\n                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n                    new_x, new_y = pos[0] + dx, pos[1] + dy\n                    if (0 <= new_x < self.m and 0 <= new_y < self.n and\n                        self.grid[new_x][new_y] != '#' and (new_x, new_y) != box and\n                        (new_x, new_y) not in visited):\n                        new_frontier.add((new_x, new_y))\n            frontier = new_frontier\n        return visited\n    \n    def reachable_neighbors_of(self, box, visited):\n        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n            new_x, new_y = box[0] + dx, box[1] + dy\n            if (new_x, new_y) in visited:\n                mir_x, mir_y = (2 * box[0] - new_x), (2 * box[1] - new_y)\n                if 0 <= mir_x < self.m and 0 <= mir_y < self.n and self.grid[mir_x][mir_y] != '#':\n                    yield mir_x, mir_y\n                        \n    def minPushBox(self, grid: List[List[str]]) -> int:\n        self.grid = grid\n        self.m = len(grid)\n        self.n = len(grid[0])\n        pusher, box, target = self.init_positions()\n        \n        frontier = {(box, pusher)}\n        visited = set()\n        dist = 0\n        while frontier:\n            visited |= frontier\n            for box, _ in visited:\n                if box == target:\n                    return dist\n            \n            new_frontier = set()\n            for cur_box, cur_pusher in frontier:\n                visited_pusher = self.bfs_from_pusher(cur_pusher, cur_box)\n                for new_box in self.reachable_neighbors_of(cur_box, visited_pusher):\n                    if (new_box, cur_box) not in visited:\n                        new_frontier.add((new_box, cur_box))\n            frontier = new_frontier\n            dist += 1\n        return -1\n            \n                    \n        \n"]