Python Solution | Union-find with 4 regions
Intuition\nWe can divide each 1 x 1 square into four regions, north, east, west and south.\n\n\n\nThe main idea is to treat slashes as boundaries that separate 
# Intuition\nWe can divide each 1 x 1 square into four regions, north, east, west and south.\n\n![image.png](https://assets.leetcode.com/users/images/aadbcd11-6da0-40e9-b59c-873220563823_1673374800.1907036.png)\n\nThe main idea is to treat slashes as boundaries that separate regions.\n\nFor example, if a square contains a slash, you can think of it as a boundary that separates a square into two parts: one containing the north and the west regions, and one containing the south and east regions.\n\n![image.png](https://assets.leetcode.com/users/images/3b121a88-3a7b-4b5c-bb8e-24530837dee9_1673374987.1677072.png)\n\nThus, we can find and merge the regions together when they are separated by different characters. In this case, this square would have a total of two connected regions.\n\nTo accomplish this, the best way is to use the union-find method. Union-find data structure keeps track of the number of connected regions. If you are not familiar with union find, check out https://algo.monster/problems/dsu_intro to learn how it works and the standard template to implement union-find.\n\n# Approach\nWe first store the \u201Croots\u201D of each region in a dictionary, where the keys are the regions and the values are their roots. Initially, each region is its own root. When two regions are unioned together, their roots become the same.\n\nWe will denote each region with the tuple \u201C(i, j, direction)\u201D. For example, (0,0, N) represents the north region of the square on the first row and the first column.\n\nWe will iterate over the squares of the grid, and use the \u201Cunion\u201D operation to merge the regions based on the characters given.\n\nFor each square, if the character is slash, we connect the north region to the west region and connect the south region to the east region of the square.\n\n![image.png](https://assets.leetcode.com/users/images/9496d5ec-5bee-407e-a68e-f9a5f83861d1_1673375435.9309077.png)\n\nElse if the character is back slash, we connect the north region to the east region and connect the south region to the west region of the square.\n\n![image.png](https://assets.leetcode.com/users/images/7ebe2af1-58f6-470e-9bd3-1f7451123955_1673375570.3362749.png)\n\nElse if the character is blank space, we connect four regions together.\n\n![image.png](https://assets.leetcode.com/users/images/527fe76b-ff12-494f-9fa0-c3ec9b932031_1673375589.0337164.png)\n\nFor two horizontally adjacent squares, the east region of the left square will always be connected to the west region of the right square. Also, for two vertically adjacent squares, the south region of the top square will always be connected to the north region of the bottom square.\n\nTo get the answer, we can count and return the number of distinct roots among all regions in the dictionary.\n\n# Complexity\n- Time complexity:\nWe can write a nested loop, where the outer loop goes through each row in the grid and the inner loop goes through each column in the grid. So the time complexity is O(N^2).\n\n- Space complexity:\nThe time complexity is O(N^2).\n\n# Code\n```\nclass Solution(object):\n    def regionsBySlashes(self, grid):\n        """\n        :type grid: List[str]\n        :rtype: int\n        """\n        roots = {}\n        #union find\n        def find(x):\n            if x not in roots:\n                roots[x] = x\n            while (x != roots[x]):\n                x = roots[x]\n            return x\n        def union(x, y):\n            roots[find(x)] = find(y)\n        length = len(grid)\n        for i in range(length):\n            for j in range(length): \n                #check if the character is \'/\'\n                if grid[i][j] == \'/\':\n                    union((i, j, \'N\'), (i, j, \'W\'))\n                    union((i, j, \'S\'), (i, j, \'E\'))\n                #check if the character is \'\\\'\n                elif grid[i][j] == \'\\\\\':\n                    union((i, j, \'N\'), (i, j, \'E\'))\n                    union((i, j, \'S\'), (i, j, \'W\'))\n                #check if the character is \' \'\n                elif grid[i][j] == \' \':\n                    union((i, j, \'N\'), (i, j, \'E\'))\n                    union((i, j, \'S\'), (i, j, \'W\'))\n                    union((i, j, \'N\'), (i, j, \'W\'))    \n                #check horizontally adjacent squares,\n                #union the E from the left square with W from the right square\n                if j > 0:\n                    union((i, j-1, \'E\'), (i, j, \'W\'))\n                #check vertcally adjacent squares,\n                #union the S from the top square with N from the bottom square\n                if i > 0:\n                    union((i-1, j, \'S\'), (i, j, \'N\'))    \n        return len(set(map(find, roots)))\n```\nCheck out the video solution for this problem:\nhttps://www.youtube.com/watch?v=LKHE5AVTmTk\n\n\nFollow our Youtube channel for new updates:\nhttps://www.youtube.com/@algo.monster\n\n\n
['Python']