[Python] 0-1 BFS with comments and explanation
Each node in our graph will contain state of box, person and the minimum cost to reach it.\n- We do a 0-1 BFS where 0 is the cost between vertices where a perso
- Each node in our graph will contain state of box, person and the minimum cost to reach it.\n- We do a 0-1 BFS where 0 is the cost between vertices where a person can reach without having to move the box, and 1 is the cost between vertices where box moved.\n- For more explanation on 0-1 BFS, watch [this video](https://www.youtube.com/watch?v=2RDQVW7RspM), or read [this article](https://cp-algorithms.com/graph/01_bfs.html)\n- By nature of BFS we reach the target with minimum cost path first, or we return not possible.\n- Time complexity is `O(M*N*M*N)` as we go through all the vertices in the worst case.\n\n```Python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        m, n = len(grid), len(grid[0])\n        is_valid = lambda x, y: 0 <= x < m and 0 <= y < n and grid[x][y] != \'#\'\n        reached = lambda x, y: (x, y) == target\n\t\t# we use these to move to the neighboring states\n        dist_row, dist_col = [0, 0, 1, -1], [1, -1, 0, 0]\n\n        def get_neighbors(state):\n            bx, by, mx, my = state\n            new_states = []\n            \n            # generate all possible states you can move to\n            for i in range(4):\n                X, Y = mx + dist_row[i], my + dist_col[i]\n                # ignore out of bounds and walls\n                if not is_valid(X, Y): continue\n                if (X, Y) == (bx, by):\n                    if is_valid(bx + dist_row[i], by + dist_col[i]):\n                        # move box if current person state is neighbor of box and valid move exists\n                        # the cost for move in this case would be 1\n                        new_states.append((bx + dist_row[i], by + dist_col[i], X, Y, 1))\n                else:\n                    # move the person keeping box intact. Cost will be 0.\n                    new_states.append((bx, by, X, Y, 0))\n            return new_states\n\n        # go through the grid and take a note of starting positions of box, man and target\n        for r, row in enumerate(grid):\n            for c, col in enumerate(row):\n                if grid[r][c] == \'S\':\n                    start = (r, c)\n                elif grid[r][c] == \'B\':\n                    box_start = (r, c)\n                elif grid[r][c] == \'T\':\n                    target = (r, c)\n\n        # each node of our graph will contain (box_row, box_column, man_row, man_column, cost_so_far)\n        start_state = (*box_start, *start, 0)\n\n        # we can use double ended queue for 0/1 BFS. Append to left if distance is 0, else to the right.\n        queue = collections.deque([start_state])\n\n        # keep note of already visited (box_row, box_col, man_row, man_col) positions.\n        # By nature of BFS, we visit them with lower cost path first,\n        # so we can ignore if they appear again on our path as cost would be higher.\n        visited = set()\n        while queue:\n            current = queue.popleft()\n            bx, by, mx, my, d = current\n            visited.add((bx, by, mx, my))\n            if reached(bx, by): return d  # reached target return the distance\n            for nb_details in get_neighbors((bx, by, mx, my)):\n                *neigh, dist = nb_details\n                if tuple(neigh) not in visited:\n                    if dist:\n                        queue.append((*neigh, dist + d))  # edge of weight 1\n                    else:\n                        queue.appendleft((*neigh, dist + d))  # edge of weight 0\n\n        # target can\'t be reached\n        return -1\n```\n\n\n
['Breadth-First Search', 'Python3']