O(n*m) solution using Tarjan to precauculate biconnected component
Approach\nBefore we start, I need to mention, this is definately not an answer interviewer expects you to implement. Feel free to ignore this solution if you ar
# Approach\nBefore we start, I need to mention, this is definately not an answer interviewer expects you to implement. Feel free to ignore this solution if you are just preparing for interview. They are not hiring you to paticipate coding competition.\n\nI shared this solution just want to give some inspiration to those people who have a little coding competition experience. O(n*m) is possible! Not just O(bfs*bfs).\n\nSteps:\n1. we consider each cell as vertex, 4 direction as edge, build a graph.\n2. calculate [biconnected component](https://en.wikipedia.org/wiki/Biconnected_component) for this graph.\n3. When box is at any cell, it can be considered as: removing one vertex in graph, we know the removed vertex is a cut vertex or not, thus we can use O(1) time to know if 4 cells next to it can reach each other.\n4. dp[i][j][k], mean the minimal push we need to use to reach a situation that box is at [i][j], and person is at direction[k] to the box.\n5. BFS to calculate the dp to get dp[target_x][target_y][0-4].\n\n# Complexity\n- Time complexity:\nO(n*m)\n\n- Space complexity:\nO(n*m)\n\n# Code\n```\nstruct node\n{\n    int x,y;\n    node(int xx,int yy)\n    {\n        x=xx;y=yy;\n    }\n};\n\nstruct node2\n{\n    int x,y,dir;\n    node2(int xx,int yy,int dd)\n    {\n        x=xx;y=yy;dir=dd;\n    }\n};\n\nclass Solution {\n    vector<vector<int>>dfn;\n    vector<vector<vector<int>>>color;\n    vector<vector<vector<bool>>>cover;\n    vector<vector<int>>mi;\n    vector<vector<char>>grid;\n    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};\n    int id;\n    int sid;\n    vector<vector<bool>>ins;\n    stack<node2>st;\n    int n,m;\n    \n    void dfs(int x,int y,int last_dir)\n    {\n        dfn[x][y]=mi[x][y]=++id;\n        int i;\n\n        for(i=0;i<4;i++)\n        {\n            if((last_dir^1)==i)\n            {\n                continue;\n            }\n            int nx,ny;\n            nx=x+dir[i][0];\n            ny=y+dir[i][1];\n\n            if(nx>=0 && nx<n && ny>=0 && ny<m && grid[nx][ny]!=\'#\')\n            {\n                if(cover[x][y][i]==0 && cover[nx][ny][i^1]==0)\n                {\n                    st.push(node2(x,y,i));\n                    cover[x][y][i]=cover[nx][ny][i^1]=1;\n                }\n                if(dfn[nx][ny]==0)\n                {\n                    dfs(nx,ny,i);\n                    if(dfn[x][y]<=mi[nx][ny])\n                    {\n                        node2 now(0,0,0);\n                        do\n                        {\n                            now=st.top();\n                            st.pop();\n                            color[now.x][now.y][now.dir]=sid;\n                            color[now.x+dir[now.dir][0]][now.y+dir[now.dir][1]][now.dir^1]=sid;\n                        }while(now.x!=x || now.y!=y || now.dir!=i);\n                        sid++;\n                    }\n                    mi[x][y]=min(mi[x][y],mi[nx][ny]);\n                }\n                else // if(ins[nx][ny]==1)\n                {\n                    mi[x][y]=min(mi[x][y],dfn[nx][ny]);\n                }\n            }\n        }\n        return;\n    }\n\npublic:\n    int minPushBox(vector<vector<char>>& grid) {\n        this->grid=grid;\n        n=grid.size();\n        m=grid[0].size();\n        int i,j,k;\n        dfn=vector<vector<int>>(n,vector<int>(m,0));\n        color=vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(4,0)));\n        cover=vector<vector<vector<bool>>>(n,vector<vector<bool>>(m,vector<bool>(4,0)));\n        mi=vector<vector<int>>(n,vector<int>(m,INT_MAX));\n        ins=vector<vector<bool>>(n,vector<bool>(m,0));\n        id=0;\n        sid=1;\n        for(i=0;i<n;i++)\n        {\n            for(j=0;j<m;j++)\n            {\n                if(grid[i][j]!=\'#\' && dfn[i][j]==0)\n                {\n                    dfs(i,j,-1);\n                }\n            }\n        }\n\n        int sx,sy,ex,ey,bx,by;\n        for(i=0;i<n;i++)\n        {\n            for(j=0;j<m;j++)\n            {\n                if(grid[i][j]==\'S\')\n                {\n                    sx=i;sy=j;\n                }\n\n                if(grid[i][j]==\'T\')\n                {\n                    ex=i;ey=j;\n                }\n\n                if(grid[i][j]==\'B\')\n                {\n                    bx=i;by=j;\n                }\n            }\n        }\n\n        ins=vector<vector<bool>>(n,vector<bool>(m,0));\n        queue<node>q;\n        queue<node2>q2;\n        q.push(node(sx,sy));\n        ins[sx][sy]=1;\n        int dp[n][m][4];\n        memset(dp,-1,sizeof(dp));\n\n        while(!q.empty())\n        {\n            node now=q.front();\n            q.pop();\n            for(i=0;i<4;i++)\n            {\n                int nx,ny;\n                nx=now.x+dir[i][0];\n                ny=now.y+dir[i][1];\n                if(nx>=0 && nx<n && ny>=0 && ny<m)\n                {\n                    if(nx==bx && ny==by)\n                    {\n                        dp[bx][by][i^1]=0;\n                        q2.push(node2(bx,by,i^1));\n                    }\n                    else if(grid[nx][ny]!=\'#\' && ins[nx][ny]==0)\n                    {\n                        ins[nx][ny]=1;\n                        q.push(node(nx,ny));\n                    }\n                }\n            }\n        }\n\n        while(!q2.empty())\n        {\n            node2 now=q2.front();\n            q2.pop();\n\n            if(now.x==ex && now.y==ey)\n            {\n                return dp[now.x][now.y][now.dir];\n            }\n            \n            int nx,ny;\n            \n\n            for(i=0;i<4;i++)\n            {\n                if(i==now.dir)\n                {\n                    continue;\n                }\n\n                nx=now.x+dir[i][0];\n                ny=now.y+dir[i][1];\n                if(nx>=0 && nx<n && ny>=0 && ny<m && grid[nx][ny]!=\'#\' && dp[now.x][now.y][i]==-1 && color[now.x][now.y][now.dir]==color[now.x][now.y][i])\n                {\n                    dp[now.x][now.y][i]=dp[now.x][now.y][now.dir];\n                    q2.push(node2(now.x,now.y,i));\n                }\n            }\n\n            int d=(now.dir^1);\n            nx=now.x+dir[d][0];\n            ny=now.y+dir[d][1];\n            if(nx>=0 && nx<n && ny>=0 && ny<m && grid[nx][ny]!=\'#\' && dp[nx][ny][now.dir]==-1)\n            {\n                dp[nx][ny][now.dir]=dp[now.x][now.y][now.dir]+1;\n                q2.push(node2(nx,ny,now.dir));\n            }\n        }\n\n        return -1;\n    }\n};\n```
['Biconnected Component', 'C++']