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

# 「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

# 游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

# 现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

# 玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
# 地板用字符 '.' 表示，意味着可以自由行走。
# 墙用字符 '#' 表示，意味着障碍物，不能通行。 
# 箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
# 玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
# 玩家无法越过箱子。
# 返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

# 這道題目是一個典型的廣度優先搜索（BFS）問題，結合了「玩家」和「箱子」兩個角色的移動和狀態管理。目標是找到將箱子「B」推到目標位置「T」所需的最小推動次數。

# 解題思路：

# 狀態表示：
# 我們需要追踪兩個動態變量：「玩家的位置」和「箱子的位置」。因此，每個狀態可以表示為 (player_x, player_y, box_x, box_y)。
# 為了避免重複訪問，我們需要使用一個集合 visited 來記錄已經訪問過的狀態。

# BFS 遍歷：
# 由於要找到最短的推動次數，所以我們採用 BFS。從初始狀態開始，每一步嘗試所有可能的移動和推動，並將新狀態加入隊列中。
# 我們只計算有效的推動操作，這意味著玩家必須首先到達箱子所在的位置旁邊（且是可以進行推動的方向），然後進行推動操作。

# 判斷條件：
# 當箱子被推到目標位置時，返回當前的推動次數。
# 如果無法達到目標位置，最終返回 -1。

# 因為若在死角會推不動 -> 需額外步驟判斷玩家能否從(px, py)移動到(tx, ty)而不經過箱子(bx, by)" -> (nx, ny) != (bx, by)
 
from collections import deque
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])        
        m, n = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == "S":
                    start_player = (row, col)
                elif  grid[row][col] == "B":
                    start_box  = (row, col)
                elif  grid[row][col] == "T":
                    target  = (row, col)                    


        def can_reach(px, py, bx, by, npx, npy):
            queue_p = deque([(px, py)])
            visited_p = set([(px, py)])

            while queue_p:
                cur_x, cur_y = queue_p.popleft()

                if (cur_x, cur_y) == (npx, npy):
                    return True

                for dx, dy in directions:
                    nx, ny = cur_x + dx, cur_y + dy
                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited_p and grid[nx][ny] != '#' and (nx, ny) != (bx, by):
                        visited_p.add((nx, ny))
                        queue_p.append((nx, ny))
            return False


        queue = deque([(start_player[0], start_player[1], start_box[0], start_box[1], 0)])
        visited = set((start_player[0], start_player[1], start_box[0], start_box[1]))

        while queue:
            px, py, bx, by, pushes = queue.popleft()
            for dx, dy in directions:
                nbx, nby = bx + dx, by + dy  # 新箱子位置
                npx, npy = bx - dx, by - dy  # 新玩家位置（應該推箱子的反方向）
                
                if 0 <= nbx < m and 0 <= nby < n and grid[nbx][nby] != '#' and can_reach(px, py, bx, by, npx, npy):
                    if (nbx, nby) == target:
                        return pushes + 1
                    if (npx, npy, nbx, nby) not in visited:
                        visited.add((npx, npy, nbx, nby))
                        queue.append((npx, npy, nbx, nby, pushes + 1))
        
        return -1
270