non-nested BFS with O(1) connectivity check
Up to now all these solutions here contain nested BFS/DFS/Union inside the outer BFS to check if the person can reach certain position. However, this can be don
Up to now all these solutions here contain nested BFS/DFS/Union inside the outer BFS to check if the person can reach certain position. However, this can be done in O(1) time with some preprocessing.\nNotice that after the first push, we only need to consider states with the person next to the box. In that case, we only check connnectivity between two cells both adjacent to the box with the box cell treated as a wall. Now we can see that under this circumstance the two cells are connected if and only if they are in a loop, or more generally, a 2-connected component. With a DFS we can get all the 2-connected components, and given that a cell can be in no more than 4 components, we can check connectivity in O(1) time.\nFinally we get an algorithm of one-pass DFS and one-pass BFS, with complexity O(nm) rather than O((nm)^2) for nested algorithms. The result is python3 48ms, faster than 99.70%, and the rest 0.3% is a cheater. It should be able to deal with n,m~500 cases.\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        n,m=len(grid),len(grid[0])\n        bcc=[[set() for j in range(m)] for i in range(n)]\n        low=[[0]*m for i in range(n)]\n        dfn=[[0]*m for i in range(n)]\n        T,cnt,st=0,0,[]\n        def dfs(i,j):\n            nonlocal T,cnt\n            if not (0<=i<n and 0<=j<m) or grid[i][j]==\'#\':\n                return -1\n            elif dfn[i][j]>0:\n                return 0\n            st.append((i,j))\n            T+=1\n            low[i][j]=dfn[i][j]=T\n            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n                temp=dfs(x,y)\n                if temp==-1:\n                    continue\n                elif temp==0:\n                    low[i][j]=min(low[i][j],dfn[x][y])\n                    continue\n                if low[x][y]>=dfn[i][j]:\n                    cnt+=1\n                    while True:\n                        a,b=st.pop()\n                        bcc[a][b].add(cnt)\n                        if (a,b)==(x,y):\n                            break\n                    bcc[i][j].add(cnt)\n                low[i][j]=min(low[i][j],low[x][y])\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j]!=\'#\' and dfn[i][j]==0:\n                    dfs(i,j)\n                if grid[i][j]==\'S\':\n                    sx,sy=i,j\n                elif grid[i][j]==\'T\':\n                    tx,ty=i,j\n                elif grid[i][j]==\'B\':\n                    bx,by=i,j\n        q0,visited=[(sx,sy)],[[0]*m for i in range(n)]\n        visited[sx][sy]=1\n        while q0:\n            temp=[]\n            for x,y in q0:\n                for px,py in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n                    if 0<=px<n and 0<=py<m and grid[px][py] in \'.T\' and visited[px][py]==0:\n                        visited[px][py]=1\n                        temp.append((px,py))\n            q0=temp\n        q=[(bx,by,x,y) for x,y in [(bx+1,by),(bx-1,by),(bx,by+1),(bx,by-1)] if visited[x][y]]\n        visited,ans=set(q),0\n        while q:\n            temp=[]\n            for x1,y1,x2,y2 in q:\n                #print(x1,y1,x2,y2)\n                if (x1,y1)==(tx,ty):\n                    return ans\n                x1,y1,x2,y2=x1*2-x2,y1*2-y2,x1,y1\n                if not (0<=x1<n and 0<=y1<m) or grid[x1][y1]==\'#\':\n                    continue\n                for px,py in [(x1+1,y1),(x1-1,y1),(x1,y1+1),(x1,y1-1)]:\n                    #print(px,py)\n                    if (0<=px<n and 0<=py<m) and (grid[px][py]!=\'#\') and (bcc[px][py]&bcc[x2][y2]) and ((x1,y1,px,py) not in visited):\n                        nxt=x1,y1,px,py\n                        visited.add(nxt)\n                        temp.append(nxt)\n            q,ans=temp,ans+1\n        return -1\n```
[]