aboutsummaryrefslogtreecommitdiff
path: root/regions_cut_by_slashes.py
diff options
context:
space:
mode:
Diffstat (limited to 'regions_cut_by_slashes.py')
-rw-r--r--regions_cut_by_slashes.py47
1 files changed, 47 insertions, 0 deletions
diff --git a/regions_cut_by_slashes.py b/regions_cut_by_slashes.py
new file mode 100644
index 0000000..c25a08e
--- /dev/null
+++ b/regions_cut_by_slashes.py
@@ -0,0 +1,47 @@
+# 959. Regions Cut By Slashes
+
+"""
+an 'n * n' grid is composed of 1 * 1 squares where each 1 * 1 square consists
+of a '/' or '\' or blank space ' '. these characters divide the square into
+contiguous regions. given the grid 'grid' represented as a string array,
+return the number of regions. note that backslash characters are escaped.
+"""
+
+
+class Solution(object):
+ def regionsBySlashes(self, grid):
+ """
+ :type grid: List[str]
+ :rtype: int
+ """
+ n = {}
+
+ def find(x):
+ n.setdefault(x, x)
+ if x != n[x]:
+ n[x] = find(n[x])
+ return n[x]
+
+ def union(x, y):
+ n[find(x)] = find(y)
+
+ for i in range(len(grid)):
+ for j in range(len(grid)):
+ if i:
+ union((i - 1, j, 2), (i, j, 0))
+ if j:
+ union((i, j - 1, 1), (i, j, 3))
+ if grid[i][j] != "/":
+ union((i, j, 0), (i, j, 1))
+ union((i, j, 2), (i, j, 3))
+ if grid[i][j] != "\\":
+ union((i, j, 3), (i, j, 0))
+ union((i, j, 1), (i, j, 2))
+ return len(set(map(find, n)))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.regionsBySlashes(grid=[" /", "/ "]))
+ print(obj.regionsBySlashes(grid=[" /", " "]))
+ print(obj.regionsBySlashes(grid=["/\\", "\\/"]))