c++, 2 * BFS with explanations
Intuition and observations:\n we need to count only the box moves, so let\'s kick around the box and count the moves\n for the person we need to check if he can
Intuition and observations:\n* we need to count only the box moves, so let\'s kick around the box and count the moves\n* for the person we need to check if he can walk to the place in front of the box\n* to move the box, the person have to stand in front of it:\n```\n[[".",".","."],  [[".",".","."],  [[".","S","."],  [[".","T","."],\n ["S","B","T"],   ["T","B","S"],   [".","B","."],   [".","B","."],\n [".",".","."]]   [".",".","."]]   [".","T","."]]   [".","S","."]]\n```\n* When the person moves the box, he will take the place of the box\n* Usually the person will hang around the box so BFS is preferrable\n* The box itself is an obstacle so we need to check if a person can walk separately for each box position. As a consequence, we need to track person+box positions as visited\n* The same position of the person and the box can be walkable or not depending on where the person starts. So we should mark the person+box position as visited only when it is reachable.\n* To navigate properly always use rows and cols (and never x and y) because it matches the intuition: ```grid[r][c]```. For x and y it would be ```grid[y][x]``` so don\'t do that\n\nSteps:\n* find the positions of person, box and target\n* iterate all positions reachable with one more move (and add next moves to the same list)\n* for each position try to move the box in all 4 directions (BFS #1)\n* check if the person can walk to stand in front of the box (BFS #2)\n\n```\nclass Solution {\n    int rows, cols;\n    vector<vector<int>> dirs={{1,0},{0,1},{-1,0},{0,-1}};\n    \n\t// positions: person, new_person, box\n    bool isReachable(int pr, int pc, int npr, int npc, int br, int bc, vector<vector<char>>& grid)\n    {\n        vector<int> visited(rows*cols,0);\n        visited[pr*cols+pc]=1;\n        list<vector<int>> togo; togo.push_back({pr,pc});\n        while(togo.size())\n        {\n            int r=togo.front()[0], c=togo.front()[1];\n            togo.pop_front();\n            if(r==npr && c==npc) return true;\n            for(auto& d:dirs)\n            {\n                int nr=r+d[0], nc=c+d[1], key=nr*cols+nc;\n                if(nr<0||nc<0||nr>=rows||nc>=cols||grid[nr][nc]==\'#\'||(nr==br&&nc==bc)) continue;\n                if(visited[key]) continue;\n                visited[key]=1;\n                togo.push_back({nr,nc});\n            }\n        }\n        return false;\n    }\npublic:\n    int minPushBox(vector<vector<char>>& grid) {\n        rows = grid.size(), cols=grid[0].size();\n        int pr,pc,br,bc,tr,tc; // person, box, target\n        for(int r=0;r<rows;r++)\n            for(int c=0;c<cols;c++)\n                if(     grid[r][c]==\'S\') pr=r, pc=c;\n                else if(grid[r][c]==\'B\') br=r, bc=c;\n                else if(grid[r][c]==\'T\') tr=r, tc=c;\n        \n        vector<vector<int>> visited(rows*cols,vector<int>(rows*cols,0));\n        int pkey=pr*cols+pc, bkey=br*cols+bc;\n        visited[pkey][bkey]=1;\n        queue<vector<int>> q;\n        q.push({pr,pc,br,bc});  // person.r, person.c, box.r, box.c\n\n        int moves=0;\n        while(q.size())\n        {\n            int len = q.size();\n            moves++;\n            for(int i=0; i<len; i++) // iterate throuh all positions reachable within 1 move\n            {\n                vector<int>& pos = q.front();\n                int pr=pos[0], pc=pos[1], br=pos[2], bc=pos[3];\n                q.pop();\n                for(auto& d:dirs) // try to move the box\n                {\n                    // person stands in front of the box to move it \n                    int nbr=br+d[0], nbc=bc+d[1], npr=br-d[0], npc=bc-d[1];\n                    if(nbr<0||nbc<0||nbr>=rows||nbc>=cols||grid[nbr][nbc]==\'#\') continue;\n                    if(npr<0||npc<0||npr>=rows||npc>=cols||grid[npr][npc]==\'#\') continue;\n\n                    pkey=npr*cols+npc, bkey=br*cols+bc;\n                    if(visited[pkey][bkey]==1) continue;\n                    \n                    // try to walk to the new position and consider where is the box now\n                    if(!isReachable(pr,pc,npr,npc,br,bc,grid)) continue;\n                    visited[pkey][bkey]=1; // trick: mark as visited only if we managed to get there\n                    if(nbr==tr && nbc==tc) return moves;\n                    \n                    q.push({br,bc,nbr,nbc}); // the person takes the place of the box\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n\nThis test case is the most advanced since the same position of the box and person have to be checked twice (```grid[3][4]``` to move the box up):\n```\n[["#",".",".","#","T","#","#","#","#"],["#",".",".","#",".","#",".",".","#"],["#",".",".","#",".","#","B",".","#"],["#",".",".",".",".",".",".",".","#"],["#",".",".",".",".","#",".","S","#"],["#",".",".","#",".","#","#","#","#"]]\n\n[\n["#",".",".","#","T","#","#","#","#"],   0\n["#",".",".","#",".","#",".",".","#"],   1\n["#",".",".","#",".","#","B",".","#"],   2\n["#",".",".",".",".",".",".",".","#"],   3\n["#",".",".",".",".","#",".","S","#"],   4\n["#",".",".","#",".","#","#","#","#"]]   5\n  0   1   2   3   4   5   6   7   8\n```
['Breadth-First Search']