cpp two bfs solution, 8ms beat 100%
typical bfs problem for shortest distance.\nThe person shall be able to move to the location behind the box to make a move.\nwe can use dfs/bfs to check if pers
typical bfs problem for shortest distance.\nThe person shall be able to move to the location behind the box to make a move.\nwe can use dfs/bfs to check if person can move to desired location.\nhowever dfs will get TLE since dfs is one direction forward until failure, hence dfs will use more time in average.\n\ncheck if person can move a position is a conventional bfs.\ncheck box can be moved to a position is a bit tricky, it needs both the person and box position, so we use a pair of position in the queue\nand the visited shall also use combined information, I used the string combination of the two positions.\n\n```cpp\n    int minPushBox(vector<vector<char>>& grid) {\n        //bfs with person and box, the person can move in the free cells\n        //person must be able to walk to the box.\n        int m=grid.size(),n=grid[0].size();\n        queue<pair<int,int>> q; //store the next valid box position: it shall store: player,box,\n        unordered_set<string> v;\n        int src=0,dst=0,player=0;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]==\'S\') {player=i*n+j;grid[i][j]=\'.\';}\n                if(grid[i][j]==\'B\') {src=i*n+j;grid[i][j]=\'.\';}\n                if(grid[i][j]==\'T\') {dst=i*n+j;grid[i][j]=\'.\';}\n            }\n        }\n        if(src==dst) return 0;\n        q.push({src,player});\n        int step=0;\n        int dir[][4]={{-1,0},{1,0},{0,-1},{0,1}};\n        while(q.size()){\n            int sz=q.size();\n            while(sz--){\n                auto pos=q.front();\n                q.pop();\n                int box=pos.first,player=pos.second;\n                if(box==dst) return step;\n                int xb=box/n,yb=box%n;\n                for(auto d: dir){\n                    int x=xb+d[0],y=yb+d[1]; //new box position\n                    int xp=xb-d[0],yp=yb-d[1];\n                    if(x<0||y<0||x>=m||y>=n||grid[x][y]==\'#\') continue;\n                    if(xp<0||yp<0||xp>=m||yp>=n||grid[xp][yp]==\'#\') continue;\n                    string s=to_string(box)+","+to_string(xp*n+yp);//box pos+person pos\n                    if(v.count(s)) continue;\n                    if(can_access(grid,player,xp*n+yp,box)){\n                        q.push({x*n+y,box});//make a push, box move to new, p moves to box\n                        v.insert(s);\n                    }\n                }\n            }\n            step++;\n        }\n        return -1;\n    }\n    bool can_access(vector<vector<char>>& g,int src,int dst,int box){\n        int m=g.size(),n=g[0].size();\n        //bfs shall be better than dfs\n        queue<int> q;\n        vector<bool> v(m*n);\n        q.push(src);\n        v[src]=1;\n        int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};\n        g[box/n][box%n]=\'#\';\n        while(q.size()){\n            int sz=q.size();\n            while(sz--){\n                int p=q.front();\n                q.pop();\n                if(p==dst) {g[box/n][box%n]=\'.\';return 1;}\n                int x0=p/n,y0=p%n;\n                for(auto d: dir){\n                    int x=x0+d[0],y=y0+d[1];\n                    if(x<0||y<0||x>=m||y>=n||g[x][y]!=\'.\'||v[x*n+y]) continue;\n                    v[x*n+y]=1;\n                    q.push(x*n+y);\n                }\n            }\n        }\n        g[box/n][box%n]=\'.\';\n        return 0;\n    }\n```\n\t\n
[]