title
n a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.
(Note that backslash characters are escaped, so a \ is represented as “\”.)
Return the number of regions.
Example 1:
Input:
[
" /",
"/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:
Example 2:
Input:
[
" /",
" "
]
Output: 1
Explanation: The 2x2 grid is as follows:
Example 3:
Input:
[
"\\/",
"/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:
Example 4:
Input:
[
"/\\",
"\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:
Example 5:
Input:
[
"//",
"/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:
solution
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
uf = {}
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf.setdefault(a, a)
uf.setdefault(b, b)
uf[find(a)] = find(b)
print("grid: ", grid)
n = len(grid)
def p(x, y):
return (x, y)
for i in range(n):
for j in range(n):
if grid[i][j] == "/":
union(p(i + 0.5, j), p(i, j + 0.5))
union(p(i + 1, j + 0.5), p(i + 0.5, j + 1))
elif grid[i][j] == "\\":
union(p(i + 0.5, j), p(i + 1, j + 0.5))
union(p(i, j + 0.5), p(i + 0.5, j + 1))
elif grid[i][j] == " ":
union(p(i + 0.5, j), p(i, j + 0.5))
union(p(i + 1, j + 0.5), p(i + 0.5, j + 1))
union(p(i + 0.5, j), p(i + 1, j + 0.5))
union(p(i, j + 0.5), p(i + 0.5, j + 1))
count = len({find(x) for x in uf})
print("count: ", count)
return count