<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>

from collections import deque

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

        R = len(grid)
        C = len(grid[0])
        maze = [['#']*(C+2)]

        for r in range(1,R+1):
            maze.append(['#'])
            str = grid[r-1]
            for c in range(1,C+1): 
                match str[c-1]:
                    case 'B':
                        Box = (r,c)
                    case 'S':
                        Source = (r,c)
                    case 'T':
                        Target = (r,c)

                if(str[c-1] == '#'):
                    maze[r].append('#')
                else:
                    maze[r].append('.')

            maze[r].append('#')

        maze.append(maze[0])

        layer = 0
        layermap = [[0]*(C+2) for _ in range(R+2)]
        ways = [[1,0], [0,1], [-1,0], [0,-1]]

        def reachable(source, target, layer):
            buffer = deque([source])

            while buffer:
                pos = buffer.popleft()

                if(pos == target):
                    return True

                next = [(pos[0]-1, pos[1]), (pos[0], pos[1]-1), (pos[0]+1, pos[1]), (pos[0], pos[1]+1)]

                for r, c in next:
                    if(maze[r][c] == '.' and layermap[r][c] != layer):
                        layermap[r][c] = layer
                        buffer.append((r,c))
                
            return False

        maxstep = 400
        steped = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
        buffer = deque([(Box, Source, 0)])

        while buffer:
            box, source, step = buffer.popleft()

            if(box == Target):
                maxstep = step
                break
            if(step > maxstep):
                break

            new_boxes = [(box[0]+1, box[1]), (box[0], box[1]+1), (box[0]-1, box[1]), (box[0], box[1]-1)]
            new_sources = [(box[0]-1, box[1]), (box[0], box[1]-1), (box[0]+1, box[1]), (box[0], box[1]+1)]
            w = 0

            for push_to, push_from in zip(new_boxes, new_sources):
                if(maze[push_to[0]][push_to[1]] == '.' and maze[push_from[0]][push_from[1]] == '.' and steped[push_to[0]][push_to[1]][w] == 0):
                    maze[box[0]][box[1]] = '#'
                    layer += 1

                    if(reachable(source, push_from, layer)):
                        steped[push_to[0]][push_to[1]][w] = step+1
                        buffer.append((push_to, box, step+1))

                    maze[box[0]][box[1]] = '.'

                w += 1

        if(maxstep == 400):
            return -1
        
        return maxstep
67