BFS with a heap
Note normal bfs can lead to wrong answers, since the number of pushes of which we wish to find the minimum is not necessarily increasing in the normal queue whe
Note normal bfs can lead to wrong answers, since the number of pushes of which we wish to find the minimum is not necessarily increasing in the normal queue where the step counts corresponds to, rather, the moves of the player, which include steps that are not pushes. So we need to restructure the queue using a heap to keep the step of the minimum pushes atop the heap.\n\n# Code\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \'S\':\n                    player = (i,j)\n                if grid[i][j] == \'B\':\n                    box = (i,j)\n                if grid[i][j] == \'T\':\n                    target = (i,j)\n        seen = set([(player,box)])\n        queue = [(0,player,box)]\n        heapq.heapify(queue)\n        while queue:\n            s,p,b = heapq.heappop(queue)\n            if b == target:\n                return s\n            pi,pj = p\n            bi,bj = b\n            for di,dj in [(0,1),(1,0),(-1,0),(0,-1)]:\n                ni,nj = pi+di,pj+dj\n                if (ni,nj)==(bi,bj):\n                    nbi,nbj = bi+di,bj+dj\n                    if 0<=ni<m and 0<=nj<n and 0<=nbi<m and 0<=nbj<n and grid[nbi][nbj] != \'#\' and ((ni,nj),(nbi,nbj)) not in seen:\n                        heapq.heappush(queue,(s+1,(ni,nj),(nbi,nbj)))\n                        seen.add(((ni,nj),(nbi,nbj)))\n                else:\n                    if 0<=ni<m and 0<=nj<n and grid[ni][nj] != \'#\' and ((ni,nj),(bi,bj)) not in seen:\n                        heapq.heappush(queue,(s,(ni,nj),(bi,bj)))\n                        seen.add(((ni,nj),(bi,bj)))\n        return -1\n\n\n\n        \n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python3']