Grid Expansion with explanation || BFS || Easy to understand || C++
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem of finding the number of regions formed by slashes in a given grid
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem of finding the number of regions formed by slashes in a given grid, we create an auxiliary matrix that represents the grid. Each cell in this auxiliary matrix corresponds to a 3x3 subgrid in the original grid. We mark the cells in the auxiliary matrix based on the slashes (\'/\') and backslashes (\'\\\\\') in the original grid. Next, we perform a breadth-first search (BFS) to explore each unvisited region in the auxiliary matrix. During BFS, we mark visited cells as `-1` in the auxiliary matrix and increment a counter for each unvisited region encountered. The final answer is the value of this counter. This approach efficiently identifies the regions formed by slashes. \n# Why are we expanding the grid?\nThe value of `n` is multiplied by 3 to create an expanded matrix that accurately represents the grid. Each cell in the original grid is expanded into a 3x3 subgrid in the new matrix. This expansion allows for precise tracking of regions formed by slashes (\'/\') and backslashes (\'\\\\\'). By doing so, the BFS traversal can correctly identify and explore these regions. In summary, the multiplication by 3 ensures that the expanded matrix covers all possible regions in the grid, improving the accuracy of the algorithm.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Create an Auxiliary Matrix:**\n   - We initialize an auxiliary matrix called `matrix` with dimensions `n * 3 x n * 3`, where `n` is the size of the original grid.\n   - Each cell in the auxiliary matrix corresponds to a 3x3 subgrid in the original grid.\n\n2. **Mark Cells in the Auxiliary Matrix:**\n   - For each cell `(i, j)` in the original grid:\n     - Calculate the corresponding row and column indices in the auxiliary matrix: `row = i * 3`, `col = j * 3`.\n     - If `grid[i][j]` contains \'/\', mark the cells in the auxiliary matrix as follows:\n       - `matrix[row][col + 2] = 1`\n       - `matrix[row + 1][col + 1] = 1`\n       - `matrix[row + 2][col] = 1`\n     - If `grid[i][j]` contains \'\\\\\', mark the cells in the auxiliary matrix similarly.\n\n3. **Breadth-First Search (BFS):**\n   - Initialize a counter `cnt` to keep track of the number of regions.\n   - Iterate through the auxiliary matrix:\n     - For each unvisited cell `(i, j)` with `matrix[i][j] == 0`:\n       - Start a BFS from `(i, j)` to explore the region.\n       - Mark visited cells as `-1` in the auxiliary matrix.\n       - Increment `cnt` for each unvisited region encountered during BFS.\n\n4. **Return the Answer:**\n   - The final answer is the value of `cnt`, representing the number of regions formed by slashes.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code\n```\nclass Solution {\npublic:\n    void bfs(int i, int j, vector<vector<int>>& matrix) {\n        int n = matrix.size();\n        queue<pair<int, int>> q;\n        q.push({i, j});\n        matrix[i][j] = -1; // to mark it as visited\n        while (!q.empty()) {\n            pair<int, int> current = q.front();\n            int row = current.first;\n            int col = current.second;\n            q.pop();\n            if (row - 1 >= 0 && matrix[row - 1][col] == 0) { // Move up\n                matrix[row - 1][col] = -1;\n                q.push({row - 1, col});\n            }\n            if (row + 1 < n && matrix[row + 1][col] == 0) { // Move down\n                matrix[row + 1][col] = -1;\n                q.push({row + 1, col});\n            }\n            if (col - 1 >= 0 && matrix[row][col - 1] == 0) { // Move left\n                matrix[row][col - 1] = -1;\n                q.push({row, col - 1});\n            }\n            if (col + 1 < n && matrix[row][col + 1] == 0) { // Move right\n                matrix[row][col + 1] = -1;\n                q.push({row, col + 1});\n            }\n        }\n    }\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        vector<vector<int>> matrix(n * 3, vector<int>(n * 3, 0));\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                int row = i * 3, col = j * 3;\n                if (grid[i][j] == \'/\') {\n                    matrix[row][col + 2] = 1;\n                    matrix[row + 1][col + 1] = 1;\n                    matrix[row + 2][col] = 1;\n                } else if (grid[i][j] == \'\\\\\') {\n                    matrix[row][col] = 1;\n                    matrix[row + 1][col + 1] = 1;\n                    matrix[row + 2][col + 2] = 1;\n                }\n            }\n        }\n        int cnt = 0;\n        for (int i = 0; i < n * 3; i++) {\n            for (int j = 0; j < n * 3; j++) {\n                if (matrix[i][j] == 0) {\n                    bfs(i, j, matrix); { cnt++; }\n                }\n            }\n        }\n        return cnt;\n    }\n};\n```
['C++']