<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:
#         direction=[[1,0],[-1,0],[0,1],[0,-1]]
#         def dijkstra(start,end,box):
#             if end[0]<0 or end[0]>=len(grid) or end[1]<0 or end[1]>=len(grid[0]) or grid[end[0]][end[1]]=="#":
#                 return False
#             heap=[(0,start[0],start[1])]
#             visited={(start[0],start[1]):0}
#             while heap:
#                 k,i,j=heappop(heap)
#                 if [i,j]==end:
#                     return True
#                 if visited[(i,j)]==k:
#                     for q,p in direction:
#                         q+=i
#                         p+=j
#                         if 0<=q<len(grid) and 0<=p<len(grid[0]) and grid[q][p]!="#" and [q,p]!=box:
#                             if (q,p) not in visited or k+1<visited[(q,p)]:
#                                 visited[(q,p)]=k+1
#                                 heappush(heap,(k+1,q,p))
#             return False


#         for i in range(len(grid)):
#             for j in range(len(grid[0])):
#                 if grid[i][j]=="#" or grid[i][j]==".":
#                     continue
#                 elif grid[i][j]=='S':
#                     start=[i,j]
#                 elif grid[i][j]=='B':
#                     box=[i,j]
#                 elif grid[i][j]=='T':
#                     end=[i,j]

#         heap=[(0,box[0],box[1],start[0],start[1])]
#         visit={(box[0],box[1],start[0],start[1]):0}
#         while heap:
#             k,i,j,s,t=heappop(heap)
#             if [i,j]==end:
#                 return k
#             if visit[(i,j,s,t)]==k:
#                 for q,p in direction:
#                     u=i+q
#                     v=j+p
#                     if 0<=u<len(grid) and 0<=v<len(grid[0]) and grid[u][v]!="#":
#                         if dijkstra([s,t],[i-q,j-p],[i,j]):
#                             if (u,v,i,j) not in visit or k+1<visit[(u,v,i,j)]:
#                                 visit[(u,v,i,j)]=k+1
#                                 heappush(heap,(k+1,u,v,i,j))
                    
#         return -1

#another a* attempt    
import math       
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        H=len(grid)
        W=len(grid[0])
        # for i in grid:
        #     print(i)
        #find position of T B S
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=="." or grid[i][j]=="#":
                    continue
                elif grid[i][j]=="S":
                    S=(i,j)
                elif grid[i][j]=="T":
                    T=(i,j)
                else:
                    B=(i,j)
                    grid[i][j]=="."
        direction=[(1,0),(-1,0),(0,1),(0,-1)]

        #if the person could move to the position of push
        def dijk(s,t,B):
            if 0<=t[0]<H and 0<=t[1]<W and grid[t[0]][t[1]]!="#":
                grid[B[0]][B[1]]="#"
                heap=[(0,s[0],s[1])]
                visited={}
                while heap:
                    cost,i,j=heap.pop()
                    if (i,j)==t:
                        grid[B[0]][B[1]]="."
                        return True
                    if (i,j) not in visited:
                        visited[(i,j)]=0
                        for u,v in direction:
                            u,v=u+i,v+j
                            if  (u,v) not in visited and 0<=u<H and 0<=v<W and grid[u][v]!="#":
                                heappush(heap,(cost+1,u,v))

                # print(s,t,B,False)
                grid[B[0]][B[1]]="."
                return False
        
        
        heap=[(abs(B[0]-T[0])+abs(B[1]-T[1]),B[0],B[1],S[0],S[1])]
        visited={}
        # print("T:",T)
        while heap:
            # print(heap)
            cost,i,j,s,t=heappop(heap)
            
            if (i,j)==T:
                return int(cost)
            if (i,j,s,t) not in visited:
                visited[(i,j,s,t)]=0
                for u,v in direction:
                    p,q=u+i,v+j
                    if  (p,q,i,j) not in visited and 0<=p<H and 0<=q<W and grid[p][q]!="#":
                        
                        if dijk((s,t),(i-u,j-v),(i,j)):
                            hyp=(abs(p-T[0])+abs(q-T[1]))
                            heappush(heap,(cost-(abs(i-T[0])+abs(j-T[1]))+hyp+1,p,q,i,j))
        return -1

##-----------------------------------above dijkstra and below a*
        # heap=[(0,B[0],B[1],S[0],S[1])]
        # visited={}
        # while heap:
        #     cost,i,j,s,t=heappop(heap)
        #     if (i,j)==T:
        #         return cost
        #     if (i,j,s,t) not in visited:
        #         visited[(i,j,s,t)]=0
        #         for u,v in direction:
        #             p,q=u+i,v+j
        #             if  (p,q,s,t) not in visited and 0<=p<H and 0<=q<W and grid[p][q]!="#":
        #                 if dijk((s,t),(i-u,j-v),(i,j)):
        #                     heappush(heap,(cost+1,p,q,i,j))

        # return -1
120