Fast easy to understand solution using 2 BFSs [intuition+diagram+explanation]
Little improvisation of the solution provided by sguo-lq, and also explaining every step and the intuition for the approach.\n\nDon\'t panic by seeing the lengt
Little improvisation of the solution provided by [sguo-lq](https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/432593/cpp-two-bfs-solution-8ms-beat-100), and also explaining every step and the intuition for the approach.\n\n**Don\'t panic by seeing the length of the solution it is actually the implementation of 2 BFSs that makes it long.**\nP.S - You know the no. of lines required for implementing a single BFS \uD83D\uDE1C.\n\nOur goal is that the box reaches the target and for that we need a BFS to get the shortest distance between the source and destination of it.\nNow the twist is we need to use the storekeeper to push it to the destination and thus here our goal is to bring him to the position adjacent to the box from where he can push the box towards the direction that would led the box\'s travelling in the shortest path given by the box\'s BFS.\n\nTo achieve the above objective we need to maintain a BFS of the box and also for each step taken by the box we need to align the storekeeper to the required adjacent cell so that the box can be pushed in the required direction provided by the box\'s BFS. \nFrom above we can infer that the storekeeper needs to be just behind the box w.r.t the direction in which it is to be pushed.\n\nLet\'s Understand pictorially:\nInitial condition (the empty cells are marked by there coresponding cell numbers): \n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\tB\t22\t#\t\n#\t25\t26\t27\t28\t29\t30\t#\t\n#\t33\t34\t35\t#\t37\tS\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nFrom above the shortest route for the box would be B -> 29 -> 28 -> 27 -> 19 -> T,\nbut the storekeeper needs to push the block to T, for the above path when the box is at 27 the person cannot be anywhere but in the right part of the maze with the only opening being at 28. So for pushing the box the storekeeper must be at 35 which isn\'t possible, thus to accomodate this the shortest route for the box is modified\nB -> 29 -> 28 -> 27 -> 26 -> 18 -> 10 -> T\nTo achieve this intuitive behaviour just need to make the storekeeper to reach the correct oriented position to push the box in its shortest path.\n\nFor 1st iteration B available options are 29, 22, 13 (according to box\'s BFS, here 20 is not suitable next stop for the box as it is a wall), thus we need to check if S ```canAccess()``` 13, 20, 29 respectively, for this a second BFS is done(can use DFS too but that would check each route individually thus increasing the search time) for the storekeeper with ```src=S(i.e. 38)``` and ```dest=13```, ```dest=20```, ```dest=29```, from the 3 dests 20 isn\'t accessable as it is a wall, thus only 2 options are left 13 or 29 this ```canAccesss```.\n\nHope you got the idea how the 2 BFS traversals are done for box and storekeeper, the basic idea is very simple get the possible next stops for the box from the box\'s BFS and for each of this stops check whether the accordingly oriented cells where the storekeeper must be present to push it forward is accessible by the storekeeper from his current location using the storekeeper\'s BFS.\nTo simplify further explanation we follow the answer path of the box.\n\n13 is to be the dest of the storekeeper,\nThus now the scenario is :\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\tS\t14\t#\t\n#\t17\t18\t19\t#\tB\t22\t#\t\n#\t25\t26\t27\t28\t29\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow push box to new location and storekeeper occupies the boxes old position\nPushes = 1\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\tS\t22\t#\t\n#\t25\t26\t27\t28\tB\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow check S ```canAccess``` 30 as box is to be pushed to 28\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\t21\t22\t#\t\n#\t25\t26\t27\t28\tB\tS\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow push box to new location and storekeeper occupies the boxes old position\nPushes = 2\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\t21\t22\t#\t\n#\t25\t26\t27\tB\tS\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow check S ```canAccess``` 29 as box is to be pushed to 27, push box to new location\nPushes = 3\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\t21\t22\t#\t\n#\t25\t26\tB\tS\t29\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow for B possible next choices are 35, 19, 26. For these the storekeeper should be at 19, 35, 28 respectively. Using the ```canAccess``` the only option is to shift box to 26 as storekeeper can only access 28\nPushes = 4\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\t18\t19\t#\t21\t22\t#\t\n#\t25\tB\tS\t28\t29\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nNow box has choice 34, 27, 18, 25 correspondingly  the respective locations for the storekeeper to be present are 18, 25, 34, 27, we take the shortest path for the box (notice here choosing either 27 or 18 as next stop for box would lead to shortest answer we continue with 18)\nPushes = 5\n```\n#\t1\t2\t#\t#\t#\t#\t#\t\n#\t9\t10\tT\t#\t13\t14\t#\t\n#\t17\tB\t19\t#\t21\t22\t#\t\n#\t25\tS\t27\t28\t29\t30\t#\t\n#\t33\t34\t35\t#\t37\t38\t#\t\n#\t41\t42\t#\t#\t#\t#\t#\t\n```\nSkipping the last 2 steps as these are visible from the above state.\nThus Pushes = 7 (answer)\n\nHope the dry run helped understand the complete logic.\n\nSee through the inline comments to understand the reason for line\n```\nclass Solution {\npublic:\n    \n    vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};\n    \n    bool isValid(vector<vector<char>>&grid, int x, int y){\n        int m = grid.size(), n = grid[0].size();\n        return (x>=0 and y>=0 and x<m and y<n and grid[x][y]!=\'#\');\n    }\n    \n    bool canAccess(vector<vector<char>>&grid, int dest, int src, int box){\n        int m = grid.size(), n = grid[0].size();\n        \n        vector<bool> visited(m*n,false);\n        visited[src] = true;\n        \n        // mark the location of box as blocked as stkp can\'t travel there\n        grid[box/n][box%n] = \'#\';\n        \n        queue<int> q;\n        q.push(src);\n        while(!q.empty()){\n            int cp = q.front();\n            q.pop();\n            if(dest==cp){grid[box/n][box%n] = \'.\';return true;}\n            for(auto e:dir){\n                int nx = cp/n+e[0], ny = cp%n+e[1];\n                int np = nx*n+ny;\n                if(np>=0 and np<m*n){\n                    if(visited[np]) continue;\n                    visited[np] = true;\n                    if(!isValid(grid,nx,ny)) continue;\n                    q.push(np);\n                }\n            }\n        }\n        grid[box/n][box%n] = \'.\';\n        return false;\n    }\n    \n    int minPushBox(vector<vector<char>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        // get position of storekeeper, box and target\n        // and mark those points as open path, i.e. \'.\'\n        int stkp, box, tar;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]==\'S\') {stkp = i*n+j;grid[i][j]=\'.\';}\n                else if(grid[i][j]==\'B\') {box = i*n+j;grid[i][j]=\'.\';}\n                else if(grid[i][j]==\'T\') {tar = i*n+j;;grid[i][j]=\'.\';}\n            }\n        }\n        if(box==tar) return 0;\n        \n        // BFSing for box to target\n        \n        // queue stores the stkp and the box locations\n        // as both needs to be kept track of while traversing\n        // for each location of the box\n        queue<pair<int,int>> q;\n        q.push({box,stkp});\n        \n        // keeping track of visited nodes for the stkp and \n        // the box simultaneously using a string\n        unordered_set<string> visited;\n        visited.insert(to_string(stkp)+" "+to_string(box));\n        \n        int pushes = 0;\n        while(!q.empty()){\n            int len = q.size();\n            while(len--){\n                auto [bo,stkpo] = q.front();\n                q.pop();\n                if(bo==tar) return pushes;\n                for(auto e:dir){\n                    int nbx = bo/n+e[0], nby = bo%n+e[1];\n                    int nstkpx = bo/n-e[0], nstkpy = bo%n-e[1];\n                    int nstkp = nstkpx*n+nstkpy, nb = nbx*n+nby;\n                    if(nstkp>=0 and nb>=0 and nstkp<m*n and nb<m*n){\n                        string key = to_string(nstkp)+" "+to_string(nb);\n                        if(visited.find(key)!=visited.end()) continue;\n                        if(!isValid(grid,nbx,nby) or !isValid(grid,nstkpx,nstkpy)) continue;\n                    \n                        // if stkp can get to the position from where he can push the box\n                        // push new position of box and new position of stkp (old position of box)\n                        // into the queue\n                        if(canAccess(grid,nstkp,stkpo,bo)){\n                            visited.insert(key);\n                            q.push({nb,bo});\n                        }\n                    }\n                }\n            }\n            // if reached this point means 1 push has been performed\n            // and the box is 1 step closer to the target\n            pushes++;\n        }\n        return -1;\n    }\n};\n```\n\nUpvote please if understood my explantion, devoted quite a bit of effort to put up this explanation, as I found it necessary as there\'s no proper explanation along with the intution behind the logic anywhere.\nThanks\nCheers\nHappy Coding
[]