Summary of BFS+BFS, BFS+DFS, BFS+UnionFind and other possible ways.
The solution to this problem can be: BFS + BFS or BFS + DFS or BFS + Union Find\nIn the code\nbi, bj, pi, pj mean the box location and person location. ti, tj m
The solution to this problem can be: BFS + BFS or BFS + DFS or BFS + Union Find\nIn the code\nbi, bj, pi, pj mean the box location and person location. ti, tj mean the target location of the person in order to push the box.\nSolution 1(BFS + BFS, runtime 160ms)\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                 \n        def bfs_person(i, j, ti, tj, bi, bj):\n            seen = set()\n            if ti>=R or tj>=C or grid[ti][tj]==\'#\':return False\n            cur_level = {(i,j)}\n            while cur_level:\n                nxt_level = set()\n                for i,j in cur_level:\n                    if (i,j)==(ti,tj):return True\n                    seen.add((i, j))\n                    for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                        r, c = i+di, j+dj\n                        if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                            nxt_level.add((r,c))\n                cur_level = nxt_level\n            return False \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            cur_level = {(i,j, pi, pj, 0)}\n            while cur_level:\n                nxt_level = set()\n                for i, j, pi, pj, d in cur_level:\n                    b_seen.add((i,j, pi, pj))\n                    if grid[i][j] == \'T\':return d\n                    for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                        r, c = i+di, j+dj\n                        if 0<=r<R and 0<=c<C and grid[r][c]!=\'#\' and (r,c, i, j) not in b_seen:\n                            ti, tj = i-di, j-dj\n                            if bfs_person(pi, pj, ti, tj, i, j):\n                                nxt_level.add((r,c,i, j, d+1))\n                cur_level = nxt_level      \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nSolution 2(BFS + DFS runtime 632 ms)\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                 \n        def dfs_person(i, j, ti, tj, bi, bj):\n            seen = set()\n            if ti>=R or tj>=C or grid[ti][tj]==\'#\':return False\n            open_list = [(i,j)]\n            while open_list:\n                i,j = open_list.pop()\n                if (i,j)==(ti,tj):return True\n                seen.add((i, j))\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                        open_list.append((r,c))\n            return False\n                        \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            cur_level = {(i,j, pi, pj, 0)}\n            while cur_level:\n                nxt_level = set()\n                for i, j, pi, pj, d in cur_level:\n                    b_seen.add((i,j, pi, pj))\n                    if grid[i][j] == \'T\':return d\n                    for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                        r, c = i+di, j+dj\n                        if 0<=r<R and 0<=c<C and grid[r][c]!=\'#\' and (r,c, i, j) not in b_seen:\n                            ti, tj = i-di, j-dj\n                            if dfs_person(pi, pj, ti, tj, i, j):\n                                nxt_level.add((r,c,i, j, d+1))\n                cur_level = nxt_level      \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nSolution 3(BFS + Union Find runtime1608 ms)\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        self.uf = {}\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n        def find(x):\n            self.uf.setdefault(x, x)\n            if self.uf[x] != x:\n                self.uf[x] = find(self.uf[x])\n            return self.uf[x]\n            \n        def union(x, y):\n            self.uf[find(y)] = find(x)\n                 \n        def union_find(i, j, bi, bj):\n            open_list = [(i,j)]\n            seen = set()\n            while open_list:\n                i,j = open_list.pop()\n                seen.add((i, j))\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                        union((i, j), (r, c))\n                        open_list.append((r, c))                   \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            cur_level = {(i,j, pi, pj, 0)}\n            while cur_level:\n                nxt_level = set()\n                for i, j, pi, pj, d in cur_level:\n                    b_seen.add((i,j, pi, pj))\n                    if grid[i][j] == \'T\':return d\n                    children = [(i+di, j+dj, i-di, j-dj) \n                                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]\n                                if 0<=i+di<R and 0<=j+dj<C and grid[i+di][j+dj]!=\'#\' and (i+di, j+dj, i, j) not in b_seen]\n                    if children:\n                        self.uf = {}\n                        union_find(pi, pj , i, j)\n                        for r, c, ti, tj in children:\n                            if find((ti, tj)) == find((pi, pj)):\n                                nxt_level.add((r,c,i, j, d+1))\n                cur_level = nxt_level      \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nSolution 4(BFS + DFS TLE) The reason that this solution is TLE might be the open_list size is too large if we keep all levels elements in the whole list. Solution 2 compares with this solution, only the open_list part is changed to only maintain the current level and next level. The speed of solution 2 is much faster and can get accepted.\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                 \n        def dfs_person(i, j, ti, tj, bi, bj):\n            seen = set()\n            if ti>=R or tj>=C or grid[ti][tj]==\'#\':return False\n            open_list = [(i,j)]\n            while open_list:\n                i,j = open_list.pop()\n                if (i,j)==(ti,tj):return True\n                seen.add((i, j))\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                        open_list.append((r,c))\n            return False                     \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            open_list = [(i,j, pi, pj, 0)]\n            for i, j, pi, pj, d in open_list:\n                b_seen.add((i,j, pi, pj))\n                if grid[i][j] == \'T\':return d\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and grid[r][c]!=\'#\' and (r,c, i, j) not in b_seen:\n                        ti, tj = i-di, j-dj\n                        if dfs_person(pi, pj, ti, tj, i, j):\n                            open_list.append((r,c,i, j, d+1))    \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nSolution 5 (BFS + DFS return a seen set 788 ms) It seems in this case union find is slower than DFS.\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                 \n        def dfs_person(i, j, bi, bj):\n            seen = set()\n            open_list = [(i,j)]\n            while open_list:\n                i,j = open_list.pop()\n                seen.add((i, j))\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                        open_list.append((r,c))\n            return seen                     \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            cur_level = {(i,j, pi, pj, 0)}\n            while cur_level:\n                nxt_level = set()\n                for i, j, pi, pj, d in cur_level:\n                    b_seen.add((i,j, pi, pj))\n                    if grid[i][j] == \'T\':return d\n                    children = [(i+di, j+dj, i-di, j-dj) \n                                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]\n                                if 0<=i+di<R and 0<=j+dj<C and grid[i+di][j+dj]!=\'#\' and (i+di, j+dj, i, j) not in b_seen]\n                    if children:\n                        seen = dfs_person(pi, pj , i, j)\n                        for r, c, ti, tj in children:\n                            if (pi, pj) in seen and (ti, tj ) in seen:\n                                nxt_level.add((r,c,i, j, d+1))\n                cur_level = nxt_level      \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nSolution 6 (BFS + DFS change data type of open_list for DFS from list to set runtime 192 ms) No idea why it can have such a significant speedup. The appending, traversing and pop speed between list and set should not be that much. Still unclear about this part.\n```python\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        R, C = len(grid), len(grid[0])\n        for i in range(R):\n            for j in range(C):\n                if grid[i][j] == \'S\':\n                    pi, pj = i, j\n                elif grid[i][j] == \'B\':\n                    bi, bj = i, j\n                 \n        def dfs_person(i, j, ti, tj, bi, bj):\n            seen = set()\n            if ti>=R or tj>=C or grid[ti][tj]==\'#\':return False\n            open_list = {(i,j)}\n            while open_list:\n                i,j = open_list.pop()\n                if (i,j)==(ti,tj):return True\n                seen.add((i, j))\n                for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                    r, c = i+di, j+dj\n                    if 0<=r<R and 0<=c<C and (r,c)!=(bi,bj) and (r,c) not in seen and grid[r][c]!=\'#\':\n                        open_list.add((r,c))\n            return False\n                        \n                \n        def bfs(i, j, pi, pj):\n            b_seen = set()\n            cur_level = {(i,j, pi, pj, 0)}\n            while cur_level:\n                nxt_level = set()\n                for i, j, pi, pj, d in cur_level:\n                    b_seen.add((i,j, pi, pj))\n                    if grid[i][j] == \'T\':return d\n                    for di, dj in [(1, 0),(-1, 0), (0, 1), (0, -1)]:\n                        r, c = i+di, j+dj\n                        if 0<=r<R and 0<=c<C and grid[r][c]!=\'#\' and (r,c, i, j) not in b_seen:\n                            ti, tj = i-di, j-dj\n                            if dfs_person(pi, pj, ti, tj, i, j):\n                                nxt_level.add((r,c,i, j, d+1))\n                cur_level = nxt_level      \n            return -1\n        return bfs(bi, bj, pi, pj)\n```\nFrom this post, hope it can be helpful for a better understanding about the difference and connections between BFS, DFS, and union-find.\n\nReference\nhttps://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/431138/Python-straightforward-BFS-solution
[]