Grid Scaling Classic Question + BFS Solution✨🏆
Regions Cut by Slashes\n\nThis repository contains the solution to the "Regions Cut by Slashes" problem. The problem involves counting distinct regions formed b
# Regions Cut by Slashes\n\nThis repository contains the solution to the "Regions Cut by Slashes" problem. The problem involves counting distinct regions formed by slashes (`\'/\'`, `\'\\\\\'`) and spaces in a grid. Each cell in the grid can potentially contribute to multiple regions depending on how the slashes are arranged.\n\n## Intuition\nThe problem involves a grid where slashes (`\'/\'`, `\'\\\\\'`) and spaces form different regions. To count the number of distinct regions, the grid is expanded so that each cell is subdivided into smaller parts to represent the impact of slashes clearly. By traversing these smaller parts, we can accurately count the regions.\n\n## Approach\n1. **Expand the Grid**: The original grid is expanded so that each cell becomes a 3x3 sub-grid. This allows for clear representation of the paths created by slashes (`\'/\'` and `\'\\\\\'`).\n\n2. **Mark Slashes**: The `scaledgrid` is populated by marking the positions affected by slashes with `1`, representing obstacles or boundaries.\n\n3. **BFS for Region Counting**: Breadth-First Search (BFS) is used to traverse the `scaledgrid`. For each unvisited cell (`0`), BFS is initiated to mark all connected cells in the current region as visited. Each BFS corresponds to discovering a new region.\n\n4. **Count Regions**: The total number of BFS runs equals the number of distinct regions.\n\n## Complexity\n- **Time complexity**:  \n  The time complexity is \\(O((3n)^2)\\), which simplifies to \\(O(n^2)\\), where `n` is the dimension of the input grid. This accounts for the time needed to traverse the expanded grid and perform BFS.\n\n- **Space complexity**:  \n  The space complexity is \\(O((3n)^2)\\), also simplifying to \\(O(n^2)\\), due to the space required to store the expanded `scaledgrid` and the BFS queue.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    vector<int> dr = {-1, 0, +1, 0};\n    vector<int> dc = {0, -1, 0, +1};\n\n    void solve(vector<vector<int>>& grid, int i, int j, int n, int m) {\n        queue<pair<int, int>> q;\n        q.push({i, j});\n        grid[i][j] = 1; \n\n        while (!q.empty()) {\n            auto node = q.front();\n            q.pop();\n\n            int row = node.first;\n            int col = node.second;\n\n            for (int k = 0; k < 4; k++) {\n                int nr = row + dr[k];\n                int nc = col + dc[k];\n\n                if (nr >= 0 && nc >= 0 && nr < n && nc < m && grid[nr][nc] == 0) {\n                    grid[nr][nc] = 1; \n                    q.push({nr, nc});\n                }\n            }\n        }\n    }\n\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        vector<vector<int>> scaledgrid(3 * n, vector<int>(3 * m, 0));\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (grid[i][j] == \'/\') {\n                    scaledgrid[3 * i][3 * j + 2] = 1;\n                    scaledgrid[3 * i + 1][3 * j + 1] = 1;\n                    scaledgrid[3 * i + 2][3 * j] = 1;\n                } \n                else if (grid[i][j] == \'\\\\\') {\n                    scaledgrid[3 * i][3 * j] = 1;\n                    scaledgrid[3 * i + 1][3 * j + 1] = 1;\n                    scaledgrid[3 * i + 2][3 * j + 2] = 1;\n                }\n            }\n        }\n\n        int count = 0;\n\n        for (int i = 0; i < 3 * n; i++) {\n            for (int j = 0; j < 3 * m; j++) {\n                if (scaledgrid[i][j] == 0) {\n                    count++;\n                    solve(scaledgrid, i, j, 3 * n, 3 * m);\n                }\n            }\n        }\n\n        return count;\n    }\n};\n
['Array', 'Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Union Find', 'Matrix', 'C++']