from heapq import heappush, heappop
from typing import List

# See utils library for canonical version
def dijkstra(source, getNbr, isDest=None):
    dest = None
    dist = {}
    queue = []
    heappush(queue, (0, source))
    while queue:
        # Grab current shortest that isn't finalized yet
        minDist, minNode = heappop(queue)
        if minNode in dist:
            # Finalized with something shorter before, continue
            assert dist[minNode] <= minDist
            continue
        # Finalize the current shortest
        dist[minNode] = minDist
        # Check if it's already at the destination
        if isDest and isDest(minNode):
            dest = minNode
            break
        # Add all neighbors that still needs to be processed
        for nbr, weight in getNbr(minNode):
            if nbr not in dist:
                heappush(queue, (minDist + weight, nbr))
            else:
                assert minDist + weight >= dist[nbr]
    return dist, dest


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


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        """Move box one step at a time.
        For each step check if player can move opposite of where you want the box to go.
        Implementation is wasteful because I thought we were optimizing for player moves too"""
        R = len(grid)
        C = len(grid[0])
        boxStart = None
        playerStart = None
        boxEnd = None
        for r in range(R):
            for c in range(C):
                if grid[r][c] == "B":
                    boxStart = (r, c)
                    grid[r][c] = "."
                if grid[r][c] == "S":
                    playerStart = (r, c)
                    grid[r][c] = "."
                if grid[r][c] == "T":
                    boxEnd = (r, c)
                    grid[r][c] = "."

        def getWalkingDist(startR, startC, endR, endC, obstacles):
            def getPlayerNbr(node):
                ret = []
                r, c = node  # player position
                for dr, dc in dirs:
                    nr = r + dr
                    nc = c + dc
                    if (
                        0 <= nr < R
                        and 0 <= nc < C
                        and grid[nr][nc] == "."
                        and (nr, nc) not in obstacles
                    ):
                        ret.append(((nr, nc), 1))
                return ret

            dist, dest = dijkstra(
                (startR, startC), getPlayerNbr, lambda node: node == (endR, endC)
            )
            if dest in dist:
                return dist[dest]
            else:
                return float("inf")

        def getBoxNbr(node):
            ret = []
            boxR, boxC, playerR, playerC = node

            for dr, dc in dirs:
                boxNr = boxR + dr
                boxNc = boxC + dc
                playerNr = boxR - dr
                playerNc = boxC - dc
                if (
                    0 <= boxNr < R
                    and 0 <= boxNc < C
                    and 0 <= playerNr < R
                    and 0 <= playerNc < C
                    and grid[boxNr][boxNc] == "."
                    and grid[playerNr][playerNc] == "."
                ):
                    dist = getWalkingDist(
                        playerR, playerC, playerNr, playerNc, [(boxR, boxC)]
                    )
                    if dist != float("inf"):
                        ret.append(((boxNr, boxNc, boxR, boxC), 1))
            return ret

        dist, dest = dijkstra(
            (*boxStart, *playerStart), getBoxNbr, lambda node: node[:2] == boxEnd
        )

        if dest in dist:
            return dist[dest]
        return -1


if __name__ == "__main__":
    assert (
        Solution().minPushBox(
            [
                ["#", "#", "#", "#", "#", "#"],
                ["#", "T", "#", "#", "#", "#"],
                ["#", ".", ".", "B", ".", "#"],
                ["#", ".", "#", "#", ".", "#"],
                ["#", ".", ".", ".", "S", "#"],
                ["#", "#", "#", "#", "#", "#"],
            ]
        )
        == 3
    )

    assert (
        Solution().minPushBox(
            [
                ["#", "#", "#", "#", "#", "#"],
                ["#", "T", "#", "#", "#", "#"],
                ["#", ".", ".", "B", ".", "#"],
                ["#", "#", "#", "#", ".", "#"],
                ["#", ".", ".", ".", "S", "#"],
                ["#", "#", "#", "#", "#", "#"],
            ]
        )
        == -1
    )

    assert (
        Solution().minPushBox(
            [
                ["#", "#", "#", "#", "#", "#"],
                ["#", "T", ".", ".", "#", "#"],
                ["#", ".", "#", "B", ".", "#"],
                ["#", ".", ".", ".", ".", "#"],
                ["#", ".", ".", ".", "S", "#"],
                ["#", "#", "#", "#", "#", "#"],
            ]
        )
        == 5
    )

    assert (
        Solution().minPushBox(
            [
                ["#", "#", "#", "#", "#", "#", "#"],
                ["#", "S", "#", ".", "B", "T", "#"],
                ["#", "#", "#", "#", "#", "#", "#"],
            ]
        )
        == -1
    )
    assert (
        Solution().minPushBox(
            [
                ["#", ".", ".", "#", "#", "#", "#", "#"],
                ["#", ".", ".", "T", "#", ".", ".", "#"],
                ["#", ".", ".", ".", "#", "B", ".", "#"],
                ["#", ".", ".", ".", ".", ".", ".", "#"],
                ["#", ".", ".", ".", "#", ".", "S", "#"],
                ["#", ".", ".", "#", "#", "#", "#", "#"],
            ]
        )
        == 7
    )