✅ 2 BFS | Easy to understand | 75% TC | 80% SC
Intuition\n1. If the box is just sitting with robotic wheels, if we want to move to target, it is a simple problem, we can just use BFS to find the shortest rou
# Intuition\n1. If the box is just sitting with robotic wheels, if we want to move to target, it is a simple problem, we can just use BFS to find the shortest route to the target (simple right, we should work on robotic wheels \uD83D\uDE1B)\n2. Now lets introduce the constraint that the person need to be standing behind the box to push it, so while verifying if the box can travel to the next position we also need to verify if the person can travel and come stand behind the box. To verify this we need another BFS.\n3. Now one additional change we need is that we cannot simply say that we are not going to reach a pos where box has already been placed, because there can be some cases where person needs to just move the box to unblock himself and get to the right position, now for this we are using a set to store the position of box and position of person.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool isValid(pair<int, int> pos, vector<vector<char>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        int ni = pos.first, nj = pos.second;\n        return ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] != \'#\';\n    }\n    bool canTravel(vector<vector<char>>& grid, pair<int, int> box,\n                               pair<int, int> per, pair<int, int> tar) {\n        int m = grid.size(), n = grid[0].size();\n        grid[box.first][box.second] = \'#\';\n        queue<pair<int, int>> q;\n        vector<vector<bool>> vis(m, vector<bool>(n, false));\n        q.push(per);\n        int dir[5] = {0, 1, 0, -1, 0};\n        while (!q.empty()) {\n            auto [i, j] = q.front();q.pop();\n            if(make_pair(i, j) == tar) {\n                grid[box.first][box.second] = \'.\';\n                return true;\n            }\n            if(vis[i][j]) continue;\n            vis[i][j] = true;\n            for (int x = 0; x < 4; x++) {\n                int ni = i + dir[x], nj = j + dir[x + 1];\n                if (ni >= 0 && ni < m && nj >= 0 && nj < n &&\n                    grid[ni][nj] != \'#\' &&\n                    !vis[ni][nj]) {\n                    q.push(make_pair(ni, nj));\n                }\n            }\n        }\n        grid[box.first][box.second] = \'.\';\n        return false;\n    }\n    int minPushBox(vector<vector<char>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        pair<int, int> box, per, tar;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == \'S\') {\n                    per = make_pair(i, j);\n                    grid[i][j] = \'.\';\n                } else if (grid[i][j] == \'T\') {\n                    tar = make_pair(i, j);\n                    grid[i][j] = \'.\';\n                } else if (grid[i][j] == \'B\') {\n                    box = make_pair(i, j);\n                    grid[i][j] = \'.\';\n                }\n            }\n        }\n\n        queue<pair<pair<int, int>, pair<int, int>>> q;\n        set<vector<int>> vis;\n        int dir[5] = {0, 1, 0, -1, 0};\n\n        q.push(make_pair(box, per));\n        int pushes = 0;\n        while (!q.empty()) {\n            for (int i = q.size(); i > 0; i--) {\n                auto [bpos, ppos] = q.front();\n                q.pop();\n                if (bpos == tar)\n                    return pushes;\n\n                if (vis.contains(\n                        {bpos.first, bpos.second, ppos.first, ppos.second}))\n                    continue;\n                vis.insert({bpos.first, bpos.second, ppos.first, ppos.second});\n\n                for (int x = 0; x < 4; x++) {\n                    int nbi = bpos.first + dir[x],\n                        nbj = bpos.second + dir[x + 1];\n                    int npi = bpos.first + (dir[x] * -1),\n                        npj = bpos.second + (dir[x + 1] * -1);\n                    if (isValid({nbi, nbj}, grid) &&\n                        isValid({npi, npj}, grid) && \n                        canTravel(grid, bpos, ppos, {npi,npj}) &&\n                        !vis.contains({nbi, nbj, npi, npj})) {\n                        q.push({{nbi, nbj}, bpos});\n                        vis.insert({bpos.first, bpos.second, npi, npj});\n                    }\n                }\n            }\n            pushes++;\n        }\n\n        return -1;\n    }\n};\n```
['C++']