[C++ 16ms/12MB]Pictures to show step-by-step problem solving
At the first sight of this problem, I was trying to use backtracking or recursion to solve until I reread the question and examples: even there is a valid path 
At the first sight of this problem, I was trying to use backtracking or recursion to solve until I reread the question and examples: even there is a valid path from box position to target position the player could still be not able to make it. Then I gave up recursion also considering it can end up with O(4^(mn)) in worst cases.\n\nBacktracking or recursion is actually depth-first-search, though breadth-first-search seems to be more suitable for this problem (we can know the number of moves easier).\n\nThen I know at least I need two queues to do breadth-first-search, one is for box, another is for player.\n\nThen the problem comes to be how to record the path, one thing off the top of my head is using "**visit[row][col]**" to keep a record of the positions that has been visited.\n\nI started to write code based on the analysis above until failed at this test case: \n\nwhere the player has to revisit a cell to get through when the box is blocking the way to the target.\n\n![image](https://assets.leetcode.com/users/images/2f8ac61a-c699-4b4d-aeb7-4cd3a8ba4627_1632904494.8413801.png)\n\nApparently just using **visit[row][col]** cannot cover this type of cases, we need to take player\'s position into account, maybe **visit[box_row][box_col][player_row][player_col]**. \n\nWhat does it mean? **It represents the minimal moves that the player needs to do when the box is at (box_row, box_col) and the player is at (player_row, player_col).**\n\nThe box can be anywhere in the grid, but do we need to know all the doable position of the player for each positon of the box?\n\nThe answer is NO, because we only care the position that is next to the box, which is up/right/down/left. For example, when the player is up the box, the box will be pushed down by the player,  when the player is on the right side of the box, the box will be pushed towards the left by the player.\n\nThis suggests us to simplify from **visit[box_row][box_col][player_row][player_col]** to **visit[box_row][box_col][direction]** to bring the space complexity from n^4 down to 4*(n^2).  0<= box_row < n,  0<= box_col < n,  direction = 4 (up/right/down/left).\n \n**visit[box_row][box_col][direction]** means the minimal moves when the player pushes the box from that direction.\n\nYou can walk through an example in the picture below, if you can understand how the numbers get calculated, it will be easy to understand the code at the end of this post.\n\n![image](https://assets.leetcode.com/users/images/8c205009-a27b-4c8a-8c40-5cba4d469f6a_1632900631.8579888.png)\n\n\n```\nclass Solution {\npublic:\n    \n// check if the player can get to (pi1, pj1) from (pi2, pj2) when the box is in (bi, bj)\n    bool canPlayerDoIt(vector<vector<char>>& grid, vector<vector<int>>& directions, int bi, int bj, int pi1, int pj1, int pi2, int pj2) {\n        if (pi1 == pi2 && pj1 == pj2)\n            return true;\n\n        vector<vector<int>> visit(grid.size(), vector<int>(grid[0].size(), 0));\n        queue<pair<int, int>> qp;\n        qp.push(pair<int, int>(pi1, pj1));\n        visit[pi1][pj1] = 1;\n\n        while (!qp.empty()) {\n            int row = qp.front().first, col = qp.front().second;\n            for (int idx = 0; idx < directions.size(); idx++) {\n                int r = row + directions[idx][0], c = col + directions[idx][1];\n                if (r<0 || c<0 || r>grid.size() - 1 || c>grid[0].size() - 1 || visit[r][c] != 0) continue;\n                if (r == pi2 && c == pj2)  return true;\n                else if (grid[r][c] != \'#\' && (r != bi || c != bj))\n                    qp.push(pair<int, int>(r, c)), visit[r][c] = 1;\n            }\n            qp.pop();\n        }\n        return false;\n    }\n\n    int minPushBox(vector<vector<char>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        int dp[20][20][4] = { 0 }; // (box_row, box_col, up/right/down/left)\n        vector<vector<int>> directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; // up, right, down, left\n        queue<pair<int, int>> qb; // queue for box\n        int ti = 0, tj = 0, pi = 0, pj = 0, bi = 0, bj = 0; //target, player, box\n\n        // find target, player, box\n        for (int i = 0; i < m; i++)\n            for (int j = 0; j < n; j++)\n                if (grid[i][j] == \'T\')\n                    ti = i, tj = j;\n                else if (grid[i][j] == \'S\')\n                    pi = i, pj = j;\n                else if (grid[i][j] == \'B\')\n                    bi = i, bj = j;\n\n        // Trying to get the minimum pushes \n        qb.push(pair<int, int>(ti, tj));\n        for (int idx = 0; idx < directions.size(); idx++) {\n            int pr = ti + 2 * directions[idx][0], pc = tj + 2 * directions[idx][1], br = ti + directions[idx][0], bc = tj + directions[idx][1];\n            if (pr >= 0 && pr < m && pc >= 0 && pc < n && grid[pr][pc] != \'#\' && grid[br][bc] != \'#\'){\n                dp[br][bc][idx] = 1;\n                if (grid[br][bc] == \'B\'){ // find the box\n                    if (canPlayerDoIt(grid, directions, br, bc, br + directions[idx][0], bc + directions[idx][1], pi, pj))\n                        return dp[br][bc][idx];\n                }\n                qb.push(pair<int, int>(br, bc));\n            }\n        }\n        qb.pop();\n\n        while (!qb.empty()){\n            int row = qb.front().first, col = qb.front().second, current = 0, move = 0;\n            for (int idx = 0; idx < directions.size(); idx++)\n                if (dp[row][col][idx] > move)\n                    move = dp[row][col][idx], current = idx;    // what if there are 1+ max values , 1+ current\n\n            for (int idx = 0; idx < directions.size(); idx++){\n                int pr = row + 2 * directions[idx][0], pc = col + 2 * directions[idx][1], br = row + directions[idx][0], bc = col + directions[idx][1];\n                if (pr >= 0 && pr < m && pc >= 0 && pc < n && grid[pr][pc] != \'#\' && grid[br][bc] != \'#\') { //&& grid[pr][pc] != \'T\' && grid[br][bc] != \'T\')\n                    if (current == idx || (dp[br][bc][idx] == 0 &&\n                            canPlayerDoIt(grid, directions, row, col, row + directions[idx][0], col + directions[idx][1], row + directions[current][0], col + directions[current][1])))\n                    {\n                        dp[br][bc][idx] = 1 + move;\n                        if (grid[br][bc] == \'B\') // FIND THE BOX\n                            if (canPlayerDoIt(grid, directions, br, bc, br + directions[idx][0], bc + directions[idx][1], pi, pj))\n                                return dp[br][bc][idx];\n                        if (dp[br][bc][idx] > dp[br][bc][(idx + 1) % 4] && dp[br][bc][idx] > dp[br][bc][(idx + 2) % 4] && dp[br][bc][idx] > dp[br][bc][(idx + 3) % 4])\n                            qb.push(pair<int, int>(br, bc));\n                    }\n                }\n            }\n            qb.pop();\n        }\n\n        return -1;\n    }\n};\n```
[]