BFS + DFS Simple C++ solution | Easy to understand with Explanation
Intuition:\n\n1. For a moment lets forget about the player and reduce our problem to what is the minimum push that is required to place the box to it\'s target?
Intuition:\n\n1. For a moment lets forget about the player and reduce our problem to `what is the minimum push that is required to place the box to it\'s target?` , the obvious answer come to our mind is to use BFS to get this answer.\n2. Now we can assume what if someone has to push the box to place it to target and we have given the player position in matrix. It is also given that player can move in all 4 directions, it means same movement is also allowed to box if we are pushing it along the way.\n3. Then we can ask ourselves.. ohh how do we do that? How can we reach box, then only we can push. We can simply use dfs to get the answer. Like if box is reachable then we might push it along the way if push is valid.\n4. Now for a moment just ignore constraint and ask ourselves what if player is doing same push again? Like if we are doing same push again then it is of no use to us. So we can store this information in a set using pair. [You can think it is as a loop in a graph]\n\nConsider below example, assume we pushed B to its right when player stands left to B. But `current` player\'s position `S\'` can be reached via different path in this matrix. So this push we save in a set and for next same push we can ignore as result will be same.\n\n\t\t\t   [["#","#","#","#","#","#"],\n               ["#","T",".",".","#","#"],\n               ["#",".","S\'","B",".","#"],\n               ["#",".",".",".",".","#"],\n               ["#",".",".",".","S","#"],\n               ["#","#","#","#","#","#"]]\n\n5. So final Idea is to first do dfs to reach box with given constraint and then add all possible push to queue [basically all its neighbor push]. \n6. To handle case where we cannot pass through the box, before we start visiting all the neighbors of current Box position , we set the value in grid to `#` and then revert it back to `.` \n\n```cpp\nclass Solution {\npublic:\n    //direction vector\n    vector<vector<int>> dir {{0,1},{0,-1},{1,0},{-1,0}};\n    \n    int minPushBox(vector<vector<char>>& grid) {\n        //rows, cols\n        int N = grid.size();\n        int M = grid[0].size();\n        \n        //intitial position\n        int target=-1, box =-1, player = -1;\n        \n        //calcluate distance of target, box, player in grid\n        for(int i=0; i<N;i++){\n            for(int j=0;j <M;j++){\n                if(grid[i][j]==\'S\'){\n                    player = i * M + j;\n                }\n                if(grid[i][j]==\'B\'){\n                    box = i*M + j;\n                }       \n                if(grid[i][j]==\'T\'){\n                    target = i*M + j;\n                }\n            }\n        }\n        //set stl to track player-box movement\n        //if already visited same path, ignore it\n        set<pair<int, int>> visited;\n        visited.insert({player, box});\n        \n        //declare queue for BFS\n        //move box to all it\'s eligible neighbor\n        queue<pair<int,int>> q;\n        q.push({player, box});\n        \n        int ans =0;\n        while(!q.empty()){\n            \n            ans++;\n            \n            //size of neighbor to be visited\n            int size = q.size();\n            \n            while(size--){\n                \n                auto f = q.front();\n                q.pop();\n                \n                //current box position \n                int box_curr = f.second;\n                //get box position in matrix\n                int box_x = box_curr/ M;\n                int box_y = box_curr % M;\n                //palyer position\n                int p = f.first;\n                \n                //make grid with box as obstacle \n                grid[box_x][box_y] = \'#\';\n                \n                for(auto &d : dir){\n                    \n                    int new_box_x = box_x + d[0];\n                    int new_box_y = box_y + d[1];\n                    \n                    int px = box_x - d[0];\n                    int py = box_y - d[1];\n                    \n                    //to be used in dfs walk by player to reach box\n                    vector<vector<int>> walk(N, vector<int>(M, 0));\n                    \n                    if(isValid(grid, new_box_x, new_box_y) && canWalk(grid, p/M, p %M, px, py, walk) && visited.count({px * M + py, new_box_x*M + new_box_y})==0){\n                        \n                        if(new_box_x == target/M && new_box_y==target%M)\n                            return ans;\n                        \n                        visited.insert({px * M + py, new_box_x * M + new_box_y});\n                        q.push({px * M + py, new_box_x * M + new_box_y});\n                    }\n                }        \n                grid[box_x][box_y] = \'.\';\n            }\n            \n        }\n            \n        return -1;\n    }\n    \n    bool isValid(vector<vector<char>>& grid, int i, int j){\n        if(i < 0 || i>=grid.size() || j <0 || j>=grid[0].size() || grid[i][j]==\'#\')\n            return false;\n        \n        return true;\n    }\n    \n    bool canWalk(vector<vector<char>>& grid, int x, int y, int i, int j, vector<vector<int>>& walk){\n        if(x==i && y==j)\n            return true;\n        \n        for(auto &d: dir){\n            int nx = x + d[0], ny = y+d[1];   \n            if(isValid(grid, nx, ny) && walk[nx][ny] == 0){\n                walk[nx][ny] = 1;\n                if(canWalk(grid, nx, ny, i, j, walk))\n                    return true;\n            }\n        }\n        return false;\n    }\n};\n```\n\nCredit : https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/431144/cpp-BFS-%2B-DFS-solution
['Depth-First Search', 'Breadth-First Search', 'C++']