Simple Approach using Expanded Grid with Flood Fill for Counting Regions
Approach\n Describe your approach to solving the problem. \nApproach 1: Expanded Grid (from Editorial LC)\n\nWhen a cell in the grid contains a slash, it effect
# Approach\n<!-- Describe your approach to solving the problem. -->\nApproach 1: Expanded Grid **(from Editorial LC)**\n\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. As you can see in Example 1, counting the regions directly is challenging since a divided cell does not always lead to an additional region.\n\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![image.png](https://assets.leetcode.com/users/images/b4f73743-34eb-4db8-955c-a6af21c1cde2_1723255603.8459182.png)\n\n\nThis transformation simplifies our task. If we treat the slashes and grid boundaries as water, and the remaining cells as land, the problem becomes analogous to the Number of Islands.\n\nWe can solve this using the flood-fill algorithm to visit each connected region in the grid. We iterate over each cell of the grid and invoke floodfill whenever we encounter an unvisited land cell. The floodfill function explores all reachable land cells from the current cell and marks them as visited. Then, we continue to iterate over each cell in the grid until we reach the next unvisited cell, which signifies the next land region. The total number of floodfill calls corresponds to the number of regions in the grid, which is our desired answer.\n\n# Complexity\n\n## Time Complexity : O(n^2)\n## Space Complexity : O(n^2)\n\n\n# Code\n```\nclass Solution:\n    def __init__(self):\n        self.my_grid = []\n\n    def floodfill(self, grid, r, c, color):\n        # Check for out-of-bounds or already colored cells\n        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != 0:\n            return\n        \n        # Color the cell\n        grid[r][c] = color\n        \n        # Flood fill in all four directions\n        self.floodfill(grid, r - 1, c, color)\n        self.floodfill(grid, r + 1, c, color)\n        self.floodfill(grid, r, c - 1, color)\n        self.floodfill(grid, r, c + 1, color)\n\n    def regionsBySlashes(self, grid: List[str]) -> int:\n        #variables\n        n = len(grid)\n        max_color = 0\n\n        #convert strings to grid with -1,0\n        self.my_grid = [[0 for i in range(n*3)] for j in range(n*3)]\n        print(self.my_grid)\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j]=="/":\n                    self.my_grid[i*3+0][j*3+2] = -1\n                    self.my_grid[i*3+1][j*3+1] = -1\n                    self.my_grid[i*3+2][j*3+0] = -1\n                elif grid[i][j]=="\\\\":\n                    self.my_grid[i*3+0][j*3+0] = -1\n                    self.my_grid[i*3+1][j*3+1] = -1\n                    self.my_grid[i*3+2][j*3+2] = -1\n                    \n        print(self.my_grid)\n\n        #apply flood fill with m as color till entire grid is not colored\n        for i in range(n*3):\n            for j in range(n*3):\n                if self.my_grid[i][j]==0:\n                    max_color += 1\n                    self.floodfill(self.my_grid, i, j, max_color)\n                \n\n        return max_color\n\n        \n        \n```
['Depth-First Search', 'Matrix', 'Counting', 'Python3']