BFS without using priority queue | O(m^2n^2) | clear explaination | Python
We could reduce this problem to a shortest distance problem in graph:\n\nConstruct graph G = (V, E) as follows:\nLet vertice v denotes game state, a.k.a (player
We could reduce this problem to a shortest distance problem in graph:\n\nConstruct graph G = (V, E) as follows:\nLet vertice v denotes game state, a.k.a (player position, box position).\nLet edge e denotes change from one game state to another, so there are at most 4 edges for a vertex: player has at most 4 choices to move right, left, up, down and if there\'s box on the way while he could push it then he could push the box. If he doesn\'t push the box to make change, the according edge weight is 0; If he pushes the box to make change, the according edge weight is 1.\n\nThen we need to calculate shortest distance from start vertex to a set of target vertices in this graph. The brute force is to use dijkstra directly; But we could do better: since edge weight can only be 0 or 1, we could use BFS with a tiny change: everytime we want to insert a neighbor we insert it at the front if the edge to the neighbor is 0 and insert it at the back if the edge to the neighbor is 1. (Think about why!) Thanks for my friend, zpt, who tells me this method when we are taking CS374 together.\n\nHere\'s the actual code:\n```\n  # method to get start position of player, box and target position\n  def get_pos(self, grid):\n        m, n = len(grid), len(grid[0])\n        player, B, T = None, None, None\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j] == \'S\':\n                    player = (i, j)\n                elif grid[i][j] == \'B\':\n                    B = (i, j)\n                elif grid[i][j] == \'T\':\n                    T = (i, j)\n        return player, B, T\n    \n\t# return true if (i,j) is in range\n    def valid(self, i, j, grid):\n        m, n = len(grid), len(grid[0])\n        return 0 <= i < m and 0 <= j < n\n    \n\t# Given current vertex (playerPos, boxPos), get its neighbors who have not been visited yet\n    def neighbors(self, playerPos, boxPos, grid, visited):\n        res = []\n        i, j = playerPos\n        bi, bj = boxPos\n        for di, dj in {(0, 1), (0, -1), (1, 0), (-1, 0)}:\n            nextI, nextJ = i + di, j + dj\n            if Solution.valid(self, nextI, nextJ, grid) and grid[nextI][nextJ] != \'#\':\n                if (nextI, nextJ) != boxPos and ((nextI, nextJ), boxPos) not in visited:\n                    res.append((0, (nextI, nextJ), boxPos))\n                elif (nextI, nextJ) == boxPos:\n                    box_nextI, box_nextJ = bi + di, bj + dj\n                    if Solution.valid(self, box_nextI, box_nextJ, grid) and grid[box_nextI][box_nextJ] != \'#\' and ((nextI, nextJ), (box_nextI, box_nextJ)) not in visited:\n                        res.append((1, (nextI, nextJ), (box_nextI, box_nextJ)))\n        return res\n    \n\t# the main method\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        player, B, T = Solution.get_pos(self, grid)\n        visited = {(player, B)}\n        queue = [(0, player, B)]\n        while queue:\n            currDis, playerPos, boxPos = queue.pop(0)\n            if boxPos == T:\n                return currDis\n            for w, nextPos, nextBox in Solution.neighbors(self, playerPos, boxPos, grid, visited):\n                if w == 0:\n                    queue.insert(0, (currDis, nextPos, nextBox))\n                else:\n                    queue.append((1 + currDis, nextPos, nextBox))\n                visited.add((nextPos, nextBox))\n        return -1\n```\n\n
[]