Easy Solution Using Array No Graphs
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be visualized as a grid where each cell is divided into 3x3 smaller cel
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be visualized as a grid where each cell is divided into 3x3 smaller cells. This approach helps in marking the slashes and backslashes in a way that avoids confusion in overlapping regions. By marking the slashes appropriately on this 3x3 grid, we can easily identify separate regions by performing a depth-first search (DFS).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Expand the Grid: Convert the given n x n grid into a 3n x 3n grid where each cell is expanded into a 3x3 block. This makes it easier to handle the slashes and backslashes.\n\n1. A \'/\' in the original grid corresponds to marking the cells (0,2), (1,1), and (2,0) in the 3x3 block.\n2. A \'\\\\\' corresponds to marking the cells (0,0), (1,1), and (2,2) in the 3x3 block.\n2. DFS for Region Counting: After marking the slashes, perform DFS on the 3n x 3n grid to count the number of connected components of unmarked cells. Each connected component corresponds to a separate region.\n\n3. Return the Count: The total number of connected components (regions) is the answer.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nT.C- O(n*n);\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nS.C- O(n*n)\n# Code\n```\nclass Solution {\npublic:\n\n    void search(vector<vector<int>> &matrix,int i,int j){\n\n        if(i<0||i>=matrix.size()||j<0||j>=matrix.size()||matrix[i][j]==1){\n            return;\n        }\n        matrix[i][j]=1;\n        search(matrix,i+1,j);\n        search(matrix,i,j-1);\n        search(matrix,i,j+1);\n        search(matrix,i-1,j);\n\n    }\n    int regionsBySlashes(vector<string>& grid) {\n       \n       int rows=grid.size();\n       int cols=grid[0].size();\n\n       vector<vector<int>> matrix(rows*3,vector<int>(cols*3,0));\n\n       for(int i=0;i<rows;i++){\n        for(int j=0;j<cols;j++){\n            if(grid[i][j]==\'/\'){\n                matrix[i*3][j*3+2]=1;\n                matrix[i*3+1][j*3+1]=1;\n                matrix[i*3+2][j*3]=1;\n            }\n            else if(grid[i][j]==\'\\\\\'){\n                matrix[i*3][j*3]=1;\n                matrix[i*3+1][j*3+1]=1;\n                matrix[i*3+2][j*3+2]=1;\n            }\n        }\n       }\n        int ans=0;\n       for(int i=0;i<rows*3;i++){\n        for(int j=0;j<cols*3;j++ ){\n            if(matrix[i][j]==0){\n                search(matrix,i,j);\n                ans++;\n            }\n        }\n       } \nreturn ans;\n\n    }\n};\n```
['C++']