<p>A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.</p>

<p>The game is represented by an <code>m x n</code> grid of characters <code>grid</code> where each element is a wall, floor, or box.</p>

<p>Your task is to move the box <code>&#39;B&#39;</code> to the target position <code>&#39;T&#39;</code> under the following rules:</p>

<ul>
	<li>The character <code>&#39;S&#39;</code> represents the player. The player can move up, down, left, right in <code>grid</code> if it is a floor (empty cell).</li>
	<li>The character <code>&#39;.&#39;</code> represents the floor which means a free cell to walk.</li>
	<li>The character<font face="monospace">&nbsp;</font><code>&#39;#&#39;</code><font face="monospace">&nbsp;</font>represents the wall which means an obstacle (impossible to walk there).</li>
	<li>There is only one box <code>&#39;B&#39;</code> and one target cell <code>&#39;T&#39;</code> in the <code>grid</code>.</li>
	<li>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 <strong>push</strong>.</li>
	<li>The player cannot walk through the box.</li>
</ul>

<p>Return <em>the minimum number of <strong>pushes</strong> to move the box to the target</em>. If there is no way to reach the target, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/11/06/sample_1_1620.png" style="width: 500px; height: 335px;" />
<pre>
<strong>Input:</strong> grid = [[&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;T&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;B&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;S&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We return only the number of times the box is pushed.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;T&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;B&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;S&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;]]
<strong>Output:</strong> -1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;T&quot;,&quot;.&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;B&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;S&quot;,&quot;#&quot;],
               [&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> push the box down, left, left, up and up.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 20</code></li>
	<li><code>grid</code> contains only characters <code>&#39;.&#39;</code>, <code>&#39;#&#39;</code>, <code>&#39;S&#39;</code>, <code>&#39;T&#39;</code>, or <code>&#39;B&#39;</code>.</li>
	<li>There is only one character <code>&#39;S&#39;</code>, <code>&#39;B&#39;</code>, and <code>&#39;T&#39;</code> in the <code>grid</code>.</li>
</ul>

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        # Chip's Challenge!???

        # brute force:
        #   both the player and the box can move
        #   want to move the box and player to the target
        #     proxy: number of pushes required to get to the target

        # current state: player position, box position, and moves

        # only box moves count toward the score, so a ton of player moves don't count
        #   > we can encounter a (br, bc) combo with fewer moves but after more total moves

        # so something more like SPFA is in order?
        # start at (pr, pc, br, bc, moves=0)
        #   only visit (pr, pc, br, bc) if current moves <= bestSoFar

        R = len(grid)
        C = len(grid[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def inBounds(r, c) -> bool:
            return 0 <= r < R and 0 <= c < C

        def offer(pr, pc, br, bc, mvs) -> None:
            """
            Checks if candidate state (pr, pc, br, bc, moves) has already been seen
            in at most as many moves before and are in bounds.

            If it's good, add to moves and q.
            """

            if not inBounds(pr, pc): return
            if not inBounds(br, bc): return

            if grid[pr][pc] == '#' or grid[br][bc] == '#': return

            mk = (pr, pc, br, bc)
            if moves.get(mk, mvs+1) <= mvs: return # visited this with <= num moves earlier

            moves[mk] = mvs
            q.append((pr, pc, br, bc, mvs))

        # find starting coordinates for ~SPFA search
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 'S':
                    sr, sc = r, c
                elif grid[r][c] == 'T':
                    tr, tc = r, c
                elif grid[r][c] == 'B':
                    br, bc = r, c

        # ~SPFA vars; search queue and current best distance
        moves = {(sr, sc, br, bc): 0}
        q = deque()
        q.append((sr, sc, br, bc, 0)) # FIX: append tuple instead of deque((fiveEltTuple)) => queue of 5 ints >:(

        best = math.inf
        while q:
            for _ in range(len(q)):
                pr, pc, br, bc, mvs = q.popleft()

                if mvs >= best-1: continue
                if mvs > moves[(pr, pc, br, bc)]: continue # preemted by a better entry enqueued later
                if br == tr and bc == tc: 
                    best = min(best, mvs)
                    continue

                for dr, dc in dirs:
                    prr, pcc = pr+dr, pc+dc
                    if prr == br and pcc == bc:
                        # push box in same direction
                        offer(prr, pcc, br+dr, bc+dc, mvs+1)
                    else:
                        # just move player
                        offer(prr, pcc, br, bc, mvs)

        return best if best < math.inf else -1
352