[cpp] BFS + DFS solution
Use BFS to solve the problem:\nFor each state  [person, box],  use dfs to find if the person can walk to the \'back\' of the box and push the box. Once the box 
Use BFS to solve the problem:\nFor each state  `[person, box]`,  use dfs to find if the person can walk to the \'back\' of the box and push the box. Once the box reaches the destination, bfs guarantees to find the optimal solution.\nBe careful with the box position since we may be obstructed by the box after we push it.\n\n(grid size `M` x `N`)\n**Time Complexity**:  `O((MN)^2)` \nIt may look like `O((MN)^3)` at the first glance, we have `O((MN)^2)` person-box states and each canReach() takes `O(MN)` time. However, for each box location, the person must be adjacent to him, so there\'re total `O(MN)` state for this bfs solution and the all time is `O((MN)^2)`.\n\n**Space complexity**: `O(M*N)`\n\nUpdate 09/05/2020: code refactored for a better view.\n```\nclass Solution {\n    int m, n;\n    vector<vector<int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n    bool valid(vector<vector<char>>& g, int x, int y) {\n        if(x < 0 || x >= m || y < 0 || y >= n || g[x][y] == \'#\') {\n            return false;\n        }\n        return true;\n    }\n    \n    bool canReach(vector<vector<char>>& g, vector<vector<bool>>& pplLoc, int x, int y, int bx, int by) {\n        if(!valid(g, x, y) || pplLoc[x][y]) {\n            return false;\n        }\n        if(bx == x && by == y) {\n            return true;\n        }\n        pplLoc[x][y] = true;\n        for(auto& d : dir) {\n            if(canReach(g, pplLoc, x + d[0], y + d[1], bx, by)) {\n                return true;\n            }\n        }\n        return false;\n    }\n    \n    \npublic:\n    typedef pair<int, int> PI;\n    typedef pair<PI, PI> PII;\n    \n    int minPushBox(vector<vector<char>>& g) {\n        m = g.size(), n = g[0].size();\n        int px, py, bx, by, gx, gy;\n        for(int x = 0; x < m; ++x) {\n            for(int y = 0; y < n; ++y) {\n                if(g[x][y] == \'S\') {\n                    px = x, py = y;\n                }else if(g[x][y] == \'B\') {\n                    bx = x, by = y;\n                }else if(g[x][y] == \'T\') {\n                    gx = x, gy = y;\n                }\n            }\n        }\n        queue<PII> q;\n        set<PII> visited;\n        q.push({{px, py}, {bx, by}});\n        visited.insert({{px, py}, {bx, by}});\n        int ans = 0;\n        while(q.size()) {\n            ans++;\n            for(int l = q.size(); l > 0; --l) {\n                auto f = q.front();\n                q.pop();\n                auto [px, py] = f.first;\n                auto [bx, by] = f.second;\n                g[bx][by] = \'#\';\n                for(auto& d : dir) {\n                    vector<vector<bool>> pplLoc(m, vector<bool>(n, false));\n                    if(canReach(g, pplLoc, px, py, bx - d[0], by - d[1])) {\n                        int nbx = bx + d[0], nby = by + d[1];\n                        if(nbx == gx && nby == gy) {\n                            return ans;\n                        }\n                        if(valid(g, nbx, nby)) {\n                            PII newState = {{bx, by}, {nbx, nby}};\n                            if(!visited.count(newState)) {\n                                visited.insert(newState);\n                                q.push(newState);\n                            }\n                        }\n                    }\n                }\n                g[bx][by] = \'.\';\n            }\n        }\n        return -1;\n    }\n};\n```
[]