C++ Solution || BFS || Easy to Understand || Fully Explanation
Approach\n\nThis problem has two sub-problems:\n    - Find the path from box to target, using BFS\n    - Find the path from player to the position which is posi
# Approach\n\nThis problem has two sub-problems:\n    - Find the path from box to target, using BFS\n    - Find the path from player to the position which is posible to push the box, using BFS\n    \nBFS state is the position of the box and the player\n\nAfter push the box, the position of player is in the box\'s previous position\n\nA 2D-Map is used to memorize the position of the box and player \n\n\n# Complexity\n- Time complexity:\nO((n*m)^2)\n\n- Space complexity:\nO((n*m)^2)\n\n# Code\n```\nclass Solution {\npublic:\n    int m, n;\n    // up: 1 , down: 2, right: 3, left: 4\n    bool valid(int x, int y, vector<vector<char>>& grid)\n    {\n        return x>=0 && x<m && y>=0 && y<n && grid[x][y]!=\'#\';\n    }\n    bool check(int x, int y, int box_x, int box_y, int t_x, int t_y, vector<vector<char>>& grid)\n    {\n        map<pair<int,int>, bool> visited;\n        queue<pair<int,int>> mem;\n        mem.push(make_pair(x,y));\n        visited[make_pair(x,y)] = true;\n        while ( !mem.empty() )\n        {\n            auto cur = mem.front();\n            int cur_x = cur.first, cur_y = cur.second;\n            if ( cur_x == t_x && cur_y == t_y ) return true;\n            mem.pop();\n            pair<int,int> new_pos[] = {{cur_x+1, cur_y}, {cur_x-1, cur_y}, {cur_x, cur_y-1},\n                                     {cur_x, cur_y+1} };\n            for ( auto u : new_pos )\n            {\n                if ( valid(u.first, u.second, grid) && !(u.first==box_x && u.second==box_y) && !visited[make_pair(u.first,u.second)] )\n                {\n                    visited[make_pair(u.first,u.second)] = true;\n                    mem.push(make_pair(u.first,u.second));\n                }\n            }\n        }\n        return false;\n    }\n    \n    int minPushBox(vector<vector<char>>& grid) \n    {\n        int b_x, b_y, t_x, t_y, s_x, s_y;\n        m = grid.size(), n = grid[0].size();\n        for ( int i = 0; i < m; i ++)\n            for ( int j = 0; j < n; j++)\n            {\n                if ( grid[i][j] == \'B\' )\n                {\n                    b_x = i;\n                    b_y = j;\n                }\n                if ( grid[i][j] == \'T\' )\n                {\n                    t_x = i;\n                    t_y = j;\n                }\n                if ( grid[i][j] == \'S\' )\n                {\n                    s_x = i;\n                    s_y = j;\n                }\n            }    \n        queue<tuple<int,int,int,int>> mem;\n        mem.push(make_tuple(b_x,b_y,s_x,s_y));\n        map<pair<int,int>, map<pair<int,int>, bool>> visited;\n        visited[make_pair(b_x, b_y)][make_pair(s_x, s_y)] = true;\n        int res = 0;\n        while( !mem.empty() )\n        {\n            int k = mem.size();\n            while ( k-- )\n            {\n                auto [x, y, p_x, p_y] = mem.front();\n                mem.pop();\n\n                if ( x == t_x && y == t_y ) return res;\n                pair<int,int> step[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n                for (int i = 0; i < 4; i++)\n                {\n                    int dx = step[i].first, dy = step[i].second;\n                    int new_x = x+dx, new_y = y+dy, p_new_x = x-dx, p_new_y = y-dy;\n                    if ( valid(new_x, new_y, grid) && valid(p_new_x, p_new_y, grid) &&\n                    check(p_x, p_y, x, y, p_new_x, p_new_y, grid) &&\n                    !visited[make_pair(new_x, new_y)][make_pair(x, y)] )\n                    {\n                        visited[make_pair(new_x, new_y)][make_pair(x, y)] = true;\n                        mem.push(make_tuple(new_x, new_y, x, y));\n                    }\n                }\n            }\n            res++;\n        }\n        return -1;\n    }\n};\n```
['C++']