Beats 90% || Easy to Understand C++ Code || DFS traversal
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen a cell in the grid contains a slash, it effectively divides it into two parts. A f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen a cell in the grid contains a slash, it effectively divides it into two parts. A forward slash divides the cell into top-left and bottom-right sections, while a backslash divides it into top-right and bottom-left sections.\nTo address this, we can magnify the grid by expanding each cell into a 3\xD73 sub-grid, with slashes represented by diagonal cells marked as barriers:\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1.Grid Expansion:**\nThe original grid is composed of cells that can contain a slash (/ or \\\\) or be empty. Each cell in the grid is conceptually divided into 3x3 smaller cells to better represent the division caused by the slashes.\nThis expansion simplifies the problem because it allows us to mark the paths more explicitly and ensure that regions separated by slashes are distinct.\nMarking the Slashes:\n\n**2.For each cell in the original grid:**\nIf there is a backslash (\\\\), the diagonal elements of the 3x3 block (i.e., top-left to bottom-right) are marked as occupied.\nIf there is a forward slash (/), the other diagonal elements (i.e., top-right to bottom-left) are marked.\nThis marking ensures that the regions divided by the slashes are represented in the expanded grid.\n\n**3.Depth-First Search (DFS) for Region Counting:**\nAfter the grid has been expanded and the slashes have been marked, the goal is to count the number of connected components (regions) formed by unmarked cells (those with a value of 0).\nA DFS is used to traverse all the connected unmarked cells, marking them as visited (changing their value to 1).\nEach DFS traversal corresponds to discovering a new region. Therefore, every time a DFS starts, the region count is incremented.\n\n**4.Counting Regions:**\nThe algorithm iterates over the entire expanded grid. Whenever it finds an unmarked cell (0), it triggers a DFS to mark the entire region, and increments the region count.\nBy the end of the traversal, the region count will represent the total number of distinct regions formed by the slashes in the grid.\n\n# Complexity\n- Time complexity: $$O(n*n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int dr[4]={0,0,1,-1},dc[4]={1,-1,0,0};\n    void dfs(int r,int c,int n,vector<vector<int>> &mat){\n        mat[r][c]=1;\n        for(int k=0;k<4;k++){\n            int nr = r + dr[k],nc = c + dc[k];\n            if(nr>=0 && nr<n && nc>=0 && nc<n && mat[nr][nc]==0)\n                dfs(nr,nc,n,mat);\n        }\n    }\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        vector<vector<int>> mat(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 r = i*3,c=j*3;\n                if(grid[i][j]!=\' \' && grid[i][j]==\'\\\\\'){\n                    mat[r][c]=1;\n                    mat[r+1][c+1]=1;\n                    mat[r+2][c+2]=1;\n                }\n                else if(grid[i][j]!=\' \' && grid[i][j]==\'/\'){\n                    mat[r][c+2]=1;\n                    mat[r+1][c+1]=1;\n                    mat[r+2][c]=1;\n                }\n            }\n        }\n        int ans=0;\n        for(int i=0;i<n*3;i++){\n            for(int j=0;j<n*3;j++){\n                if(mat[i][j]==0){\n                    dfs(i,j,(n*3),mat);\n                    ans+=1;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']