1263. Minimum Moves to Move a Box to Their Target Location.cpp
Code\n\nclass Solution {\nprivate:\n    int m, n;\n    vector<pair<int, int>> dir;\n    struct Hash {\n        size_t operator()(const vector<int> &v) const {\n
**Code**\n```\nclass Solution {\nprivate:\n    int m, n;\n    vector<pair<int, int>> dir;\n    struct Hash {\n        size_t operator()(const vector<int> &v) const {\n            return v[0] * 20 + v[1] + v[2] * 20 + v[3];\n        }\n    };\n    unordered_set<vector<int>, Hash> visited;\n    struct Hash2 {\n        size_t operator()(const vector<int> &v) const {\n            return v[0] * 20 + v[1];\n        }\n    };    \npublic:\n    int minPushBox(vector<vector<char>>& grid) {\n        m = grid.size();\n        n = grid[0].size();\n        dir = vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n        vector<int> target, box, person;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == \'S\') {\n                    person = vector<int>{i, j};\n                } else if (grid[i][j] == \'B\') {\n                    box = vector<int>{i, j};\n                } else if (grid[i][j] == \'T\') {\n                    target = vector<int>{i, j};\n                }\n            }\n        }\n        queue<vector<int>> q;\n        q.push(vector<int>{box[0], box[1], person[0], person[1]});\n        visited.insert(vector<int>{box[0], box[1], person[0], person[1]});\n        int res = 0;\n        while (!q.empty()) {\n            int N = q.size();\n            while (N--) {\n                vector<int> cur = q.front();\n                q.pop();\n                if (cur[0] == target[0] && cur[1] == target[1])\n                    return res;\n                for (auto &d : dir) {\n                    int b_row_nex = cur[0] + d.first;\n                    int b_col_nex = cur[1] + d.second;\n                    int p_row_nex = cur[0] - d.first;\n                    int p_col_nex = cur[1] - d.second;\n             if (valid(grid, b_row_nex, b_col_nex) && valid(grid, p_row_nex, p_col_nex)) {\n                        if (canReach(grid, cur, p_row_nex, p_col_nex) &&\n     visited.find(vector<int>{b_row_nex, b_col_nex, cur[0], cur[1]}) == visited.end()) {\n                            q.push(vector<int>{b_row_nex, b_col_nex, cur[0], cur[1]});\n                     visited.insert(vector<int>{b_row_nex, b_col_nex, cur[0], cur[1]});\n                        }\n                    }\n                }\n            }\n            res += 1;\n        }\n        return -1;\n    }    \n    bool canReach(vector<vector<char>> &grid, vector<int> &start, int &p_row, int &p_col) {\n        queue<vector<int>> q;\n        unordered_set<vector<int>, Hash2> visited2;\n        q.push(vector<int>{start[2], start[3]});\n        visited2.insert(vector<int>{start[2], start[3]});\n        while (!q.empty()) {\n            vector<int> cur = q.front();\n            q.pop();\n            if (cur[0] == p_row && cur[1] == p_col)\n                return true;\n            for (auto &d : dir) {\n                int row_nex = cur[0] + d.first;\n                int col_nex = cur[1] + d.second;\n     if (valid(grid, row_nex, col_nex) && !(row_nex == start[0] && col_nex == start[1]) &&\n                    visited2.find(vector<int>{row_nex, col_nex}) == visited2.end()) {\n                    q.push(vector<int>{row_nex, col_nex});\n                    visited2.insert(vector<int>{row_nex, col_nex});\n                }\n            }\n        }\n        return false;\n    }   \n    bool valid(vector<vector<char>> &grid, int row, int col) {\n        return row >= 0 && row < m && col >= 0 && col < n && grid[row][col] != \'#\';\n    }\n};\n```
['C']