[Python] Level-by-level BFS solution (similar problems listed)
Level-by-level BFS visit can be used to solve a lot of problems of finding discrete shortest distance.\nPlease see and vote for my solutions for these similar p
Level-by-level BFS visit can be used to solve a lot of problems of finding discrete shortest distance.\nPlease see and vote for my solutions for these similar problems\n[102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/1651394/Python-level-by-level-BFS-Solution)\n[127. Word Ladder](https://leetcode.com/problems/word-ladder/discuss/352659/Simple-Python-BFS-solution)\n[126. Word Ladder II](https://leetcode.com/problems/word-ladder-ii/discuss/352661/Simple-Python-BFS-solution)\n[301. Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/discuss/327481/Python-DFS-solution-with-pruning-(28-ms-beat-99.56)-%2B-BFS-solution)\n[317. Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/discuss/331983/Python-BFS-solution-(52-ms-beat-98.27))\n[529. Minesweeper](https://leetcode.com/problems/minesweeper/discuss/1651414/python-level-by-level-bfs-solution)\n[773. Sliding Puzzle](https://leetcode.com/problems/sliding-puzzle/discuss/412586/Standard-Python-BFS-solution-(level-by-level-traversal))\n[815. Bus Routes](https://leetcode.com/problems/bus-routes/discuss/1651399/Python-Level-by-level-BFS-solution)\n[854. K-Similar Strings](https://leetcode.com/problems/k-similar-strings/discuss/420506/Python-BFS-solution)\n[864. Shortest Path to Get All Keys](https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/364604/Simple-Python-BFS-Solution-(292-ms-beat-97.78))\n[1091. Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/313229/Python-BFS-solution)\n[1210. Minimum Moves to Reach Target with Rotations](https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/discuss/392940/Standard-Python-BFS-solution)\n[1263. Minimum Moves to Move a Box to Their Target Location](https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/431138/Python-straightforward-BFS-solution)\n[1293. Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/discuss/1651383/Python-level-by-level-BFS-Solution)\n\n\n\n```\nStraightforward BFS:\n(1) find the positions of the box and player (x_B, y_B, x_S, y_S), reset the cells to be \'.\'\n(2) use (x_B, y_B, x_S, y_S) to represent the state\n      (i) find the valid next steps to move the box (x_B, y_B) to its possible neighbors: \n\t      one move is valid if one neighbor is empty and the opposite neighbor is connected to (x_S, y_S)\n\t  (ii) use BFS to to check the opposite neighbor is connected to (x_S, y_S) or not\n(3) traverse all possible states level-by-level\n```\n    \n\n```\n    def minPushBox(self, grid: List[List[str]]) -> int:        \n        def bfs_to_reach_S(r, c, x_B, y_B, x_S, y_S):\n            curr_level = {(r, c)}\n            visited = set()\n            while curr_level:\n                next_level = set()\n                for i, j in curr_level:\n                    visited.add((i, j))\n                    if i == x_S and j == y_S:\n                        return True\n                    for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n                        i1, j1 = i + di, j + dj\n                        if 0 <= i1 < n and 0 <= j1 < m and (i1, j1) not in visited and (i1, j1) != (x_B, y_B) and grid[i1][j1] != \'#\':\n                            next_level.add((i1, j1))\n                curr_level = next_level\n            return False\n            \n        def valid_moves(grid, x_B, y_B, x_S, y_S):\n            next_moves = []\n            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:\n                r1, c1 = x_B + dx, y_B + dy\n                r2, c2 = x_B - dx, y_B - dy\n                if 0 <= r1 < n and 0 <= c1 < m and grid[r1][c1] != \'#\' and 0 <= r2 < n and 0 <= c2 < m and grid[r2][c2] != \'#\':\n                    if bfs_to_reach_S(r1, c1, x_B, y_B, x_S, y_S):\n                        next_moves.append((r2, c2, x_B, y_B))\n            return next_moves\n        \n        n, m = len(grid), len(grid[0])\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] == \'B\':\n                    x_B, y_B = i, j\n                elif grid[i][j] == \'S\':\n                    x_S, y_S = i, j\n        grid[x_B][y_B], grid[x_S][y_S] = \'.\', \'.\'\n        curr_level = {(x_B, y_B, x_S, y_S)}\n        visited = set()\n        moves = 0\n        while curr_level:\n            next_level = set()\n            for i_B, j_B, i_S, j_S in curr_level:\n                visited.add((i_B, j_B, i_S, j_S))\n                if grid[i_B][j_B] == \'T\':\n                    return moves\n                for i_B1, j_B1, i_S1, j_S1 in valid_moves(grid, i_B, j_B, i_S, j_S):\n                    if (i_B1, j_B1, i_S1, j_S1) not in visited:\n                        next_level.add((i_B1, j_B1, i_S1, j_S1))\n            curr_level = next_level\n            moves += 1\n        return -1\n```
[]