Bidirectional Search+ A* Search (70 ms Beats 100%)
\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        directions = [(0,-1), (0,1)
```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        directions = [(0,-1), (0,1), (-1,0), (1,0)] # left, right, up, down\n\n        found = 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                    mi, mj = i, j\n                    found += 1\n                    if found == 3:\n                        break\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                    found += 1\n                    if found == 3:\n                        break\n                else:\n                    ti, tj = i, j\n                    found += 1\n                    if found == 3:\n                        break\n            if found == 3:\n                break\n\n        def can_push(mi, mj, bi, bj):\n            \'\'\'Uses a bidirectional search\'\'\'\n            res = [False] * 4\n\n            banned = set()\n            for i in range(4):\n                di, dj = directions[i]\n                bii, bjj = bi + di, bj + dj\n                if bii < 0 or bjj < 0 or bii >= m or bjj >= n or grid[bii][bjj] == \'#\':\n                    banned.add(i//2)\n\n            targets = {}\n            for i in range(4):\n                if i//2 in banned:\n                    continue\n                di, dj = directions[i]\n                ti, tj = bi - di, bj - dj\n                targets[(ti, tj)] = i\n\n            if not targets:\n                return res\n\n            stop = len(targets)\n            found = 0\n            q = deque([(mi, mj)])\n            visited = {(mi, mj)}\n            while q:\n                i, j = q.popleft()\n\n                if (i, j) in targets:\n                    res[targets[(i, j)]] = True\n                    found += 1\n                    if found == stop:\n                        break\n                \n                for di, dj in directions:\n                    ii, jj = i + di, j + dj\n                    if ii < 0 or jj < 0 or ii >= m or jj >= n or grid[ii][jj] == \'#\':\n                        continue\n                    if (ii, jj) == (bi, bj):\n                        continue\n                    if (ii, jj) in visited:\n                        continue\n                    visited.add((ii, jj))\n                    q.append((ii, jj))\n            return res\n\n        q = deque()\n        visited = set()\n        pushes = can_push(mi, mj, bi, bj)\n        for k in range(4):\n            di, dj = directions[k]\n            if pushes[k]:\n                ii, jj, bii, bjj = bi - di, bj - dj, bi, bj\n                q.append((ii, jj, bii, bjj))\n                visited.add((ii, jj, bii, bjj))\n\n        def h(bi, bj):\n            \'\'\'Heuristic function\'\'\'\n            return abs(bi - ti) + abs(bj - tj)\n\n        minHeap = []\n        visited = set()\n        pushes = can_push(mi, mj, bi, bj)\n        for k in range(4):\n            di, dj = directions[k]\n            if pushes[k]:\n                ii, jj, bii, bjj = bi - di, bj - dj, bi, bj\n                minHeap.append( (h(bii, bjj), 0, ii, jj, bii, bjj) ) # f, d, i, j, bi, bj\n\n        while minHeap:\n            f, d, i, j, bi, bj = heapq.heappop(minHeap)\n            if (bi, bj) == (ti, tj):\n                return d\n            \n            if (i, j, bi, bj) in visited:\n                continue\n            visited.add((i, j, bi, bj))\n\n            pushes = can_push(i, j, bi, bj)\n            for k in range(4):\n                di, dj = directions[k]\n                if pushes[k]:\n                    ii, jj, bii, bjj = bi, bj, bi + di, bj + dj\n                    if (ii, jj, bii, bjj) in visited:\n                        continue\n                    heapq.heappush(minHeap, (d + 1 + h(bii, bjj), d + 1, ii, jj, bii, bjj))\n        return -1\n```
['Python3']