[C++] BFS and DFS 80 lines
I am trying to be as "clean-code" as possible.\n\ncpp\nclass Solution {\npublic:\n    int dx[4] = {0, -1, 0, 1};\n    int dy[4] = {-1, 0, 1, 0};\n    int m, n;\
I am trying to be as "clean-code" as possible.\n\n```cpp\nclass Solution {\npublic:\n    int dx[4] = {0, -1, 0, 1};\n    int dy[4] = {-1, 0, 1, 0};\n    int m, n;\n    queue<vector<int>> q;\n    unordered_set<string> seen1; // book-keeping worker and box locations\n    unordered_set<string> seen2; // book-keeping for hasPath() DFS\n    \n    int minPushBox(vector<vector<char>>& grid) {\n        m = grid.size();\n        n = grid[0].size();\n        int bx, by, sx, sy, tx, ty;\n        for (int i = 0; i < m; i++){\n            for (int j = 0; j < n; ++j){\n                if (grid[i][j] == \'B\')\n                    bx = i, by = j;\n                else if (grid[i][j] == \'S\')\n                    sx = i, sy = j;\n                else if (grid[i][j] == \'T\')\n                    tx = i, ty = j;\n            }\n        }\n        \n        q.push({sx, sy, bx, by, 0});\n        seen1.insert(getKey4(sx, sy, bx, by));\n\n        int w1, w2, b1, b2;\n        int x1, x2, y1, y2;\n        while (!q.empty()){\n            w1 = q.front()[0], w2 = q.front()[1]; // worker location\n            b1 = q.front()[2], b2 = q.front()[3]; // box location\n            int steps = q.front()[4];\n            q.pop();\n            \n            if (b1 == tx and b2 == ty) return steps;\n            \n            for (int d = 0; d < 4; ++d){\n                x1 = b1 + dx[d], y1 = b2 + dy[d]; // worker push from this\n                x2 = b1 - dx[d], y2 = b2 - dy[d]; // box will move to this\n\n                if (seen1.count(getKey4(b1, b2, x2, y2))) continue;\n                if (canMove(grid, x1, y1, x2, y2, w1, w2, b1, b2)){\n                        q.push({b1, b2, x2, y2, steps + 1});\n                        seen1.insert(getKey4(b1, b2, x2, y2));\n                    }\n            }\n        }\n        return -1;\n    }\n    \n    string getKey4(int a, int b, int c, int d){\n        return to_string(a) + "#" + to_string(b) + "#" + to_string(c) + "#" + to_string(d);\n    }\n    \n    string getKey2(int a, int b){\n        return to_string(a) + "#" + to_string(b);\n    }\n\n    bool canMove(vector<vector<char>>& grid, int x1, int y1, int x2, int y2, int sx, int sy, int bx, int by){\n        if (0 > x1 or x1 >= m or 0 > y1 or y1 >= n or grid[x1][y1] == \'#\') return false;\n        if (0 > x2 or x2 >= m or 0 > y2 or y2 >= n or grid[x2][y2] == \'#\') return false;\n        seen2.clear();\n        return hasPath(grid, sx, sy, x1, y1, bx, by);\n    }\n    \n    bool hasPath(vector<vector<char>>& grid, int sx, int sy, \n             int px, int py, int bx, int by){\n        if (sx == px and sy == py) return true;\n        for (int d = 0; d < 4; ++d){\n            int x = sx + dx[d], y = sy + dy[d];\n            if (0 <= x and x < m and 0 <= y and y < n and grid[x][y] != \'#\'\n               and !seen2.count(getKey2(x, y)) and !(x == bx and y == by)){\n                seen2.insert(getKey2(x, y));\n                if (hasPath(grid, x, y, px, py, bx, by)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n};\n```
[]