Both Dijkstra and A star. Easy for comparison
\n# Dijkstra: \nAlgorithm for shortest path from origin. Only consider the distance from origin.\n\nIn essence: dijkstra is advanced BFS(breadth-first search). 
\n# Dijkstra: \nAlgorithm for shortest path from origin. Only consider the distance from origin.\n\n**In essence**: dijkstra is advanced BFS(breadth-first search). The only difference is Dijkstra search through the shorter path first. The idea is the future step of shorter path has potential to replace the current longer path.\n\n**E.g.** Imagine we have a BFS tree with next step option:1,7\nFor this conditon, if we go through 1 first, there will be chance we don\'t need to go through 7.\nMore clear: the next step of 1 is 2, 1+2=3 which is smaller than 7. And suppose it points to the same node as 7 does, we don\'t need to go through 7 at all.\n\n    start\n    |   | \n    1   7\n    |   |\n    2   |\n    \\   |\n    goal\n\n\n# Dijkstra code\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        direction=[[1,0],[-1,0],[0,1],[0,-1]]\n        def dijkstra(start,end,box): # a-star modification\n            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]]=="#":\n                return False\n            heap=[(0,start[0],start[1])]\n            visited={(start[0],start[1]):0}\n            while heap:\n                k,i,j=heappop(heap)\n                if [i,j]==end:\n                    return True\n                if visited[(i,j)]==k:\n                    for q,p in direction:\n                        q+=i\n                        p+=j\n                        if 0<=q<len(grid) and 0<=p<len(grid[0]) and grid[q][p]!="#" and [q,p]!=box:\n                            if (q,p) not in visited or k+1<visited[(q,p)]:\n                                visited[(q,p)]=k+1\n                                heappush(heap,(k+1,q,p))\n            return False\n\n\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j]=="#" or grid[i][j]==".":\n                    continue\n                elif grid[i][j]==\'S\':\n                    start=[i,j]\n                elif grid[i][j]==\'B\':\n                    box=[i,j]\n                elif grid[i][j]==\'T\':\n                    end=[i,j]\n\n        heap=[(0,box[0],box[1],start[0],start[1])]\n        visit={(box[0],box[1],start[0],start[1]):0}\n        while heap:\n            k,i,j,s,t=heappop(heap)\n            if [i,j]==end:\n                return k\n            if visit[(i,j,s,t)]==k:\n                for q,p in direction:\n                    u=i+q\n                    v=j+p\n                    if 0<=u<len(grid) and 0<=v<len(grid[0]) and grid[u][v]!="#":\n                        if dijkstra([s,t],[i-q,j-p],[i,j]):#set i-q,j-p as target to check if the position of push is available.\n                            if (u,v,i,j) not in visit or k+1<visit[(u,v,i,j)]:\n                                visit[(u,v,i,j)]=k+1\n                                heappush(heap,(k+1,u,v,i,j))\n                        \n        return -1\n\n```\n# A star\n**In essence**: It is advanced Dijkstra. \nAs mentioned, "Dijkstra only considers the distance to origin". This time we consider both distance to origin as well as distance to goal. The idea is with only distance to origin, we may go to the opposite direction from correct one. \n\n**E.g.** imagine now I am at origin, there are four directions I can choose. Up down left right. The goal is on the left, however I only consider the distance to origin so the 4 directions have the same cost which leads into inefficiency.\n\nIn short, A star just introduces the idea of direction compares to Dijkstra. \n**In code**, just replace the **\'distance to origin\'** in dijkstra to **\'distance to origin + distance to goal\'**\n\n# A star code\n```\nimport math\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        direction=[[1,0],[-1,0],[0,1],[0,-1]]\n        def dijkstra(start,end,box): # a-star modification\n            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]]=="#":\n                return False\n            heap=[(hypot(start[0]-end[0],start[1]-end[1]),start[0],start[1])]\n            visited={(start[0],start[1]):[0,hypot(start[0]-end[0],start[1]-end[1])]}\n            while heap:\n                k,i,j=heappop(heap)\n                if [i,j]==end:\n                    return True\n                \n                #Need following if statement, if the state of visited[(i,j)] will be updated. \n                #However, different from normal dijkstra, steps are guaranteed to be equal(because it is matrix). There will be no update.\n                # if sum(visited[(i,j)])==k: \n                d=visited[(i,j)][0] #dijkstra distance\n                for q,p in direction:\n                    q+=i#new pos\n                    p+=j\n                    if 0<=q<len(grid) and 0<=p<len(grid[0]) and grid[q][p]!="#" and [q,p]!=box:\n                        hyp=hypot(q-end[0],p-end[1])\n                        if (q,p) not in visited or d+1+hyp<sum(visited[(q,p)]):\n                            visited[(q,p)]=[d+1,hyp]\n                            heappush(heap,(d+1+hyp,q,p))\n            return False\n\n\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j]=="#" or grid[i][j]==".":\n                    continue\n                elif grid[i][j]==\'S\':\n                    start=[i,j]\n                elif grid[i][j]==\'B\':\n                    box=[i,j]\n                elif grid[i][j]==\'T\':\n                    end=[i,j]\n\n        heap=[(hypot(box[0]-end[0],box[1]-end[1]),box[0],box[1],start[0],start[1])]\n        visit={(box[0],box[1],start[0],start[1]):[0,hypot(box[0]-end[0],box[1]-end[1])]}#Only want the movement of box\n        while heap:\n            k,i,j,s,t=heappop(heap)\n            if [i,j]==end:\n                return visit[(i,j,s,t)][0]\n\n            #Need following if statement, if the state of visited[(i,j)] will be updated. \n            #However, different from normal dijkstra, steps are guaranteed to be equal(because it is matrix). There will be no update.\n            # if sum(visit[(i,j,s,t)])==k:\n            d=visit[(i,j,s,t)][0]\n            for q,p in direction:\n                u=i+q\n                v=j+p\n                if 0<=u<len(grid) and 0<=v<len(grid[0]) and grid[u][v]!="#":\n                    if dijkstra([s,t],[i-q,j-p],[i,j]):#set i-q,j-p as target to check if the position of push is available.\n                        hyp=hypot(u-end[0],v-end[1])\n                        if (u,v,i,j) not in visit or d+1+hyp<sum(visit[(u,v,i,j)]):\n                            visit[(u,v,i,j)]=[d+1,hyp]\n                            heappush(heap,(d+1+hyp,u,v,i,j))\n        return -1\n\n```\nHope it helps :)
['Python3']