题目
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', 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, so a '\' is represented as '\\'.
Example 1:
Input: grid = [" /","/ "] Output: 2
Example 2:
Input: grid = [" /"," "] Output: 1
Example 3:
Input: grid = ["/\\","\\/"] Output: 5 Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
Constraints:
n == grid.length == grid[i].length1 <= n <= 30grid[i][j]is either'/','\', or' '.
思路
leetcode959，非常有意思的一道题。
题目大意是，求用”/”和”\”分隔的N*N正方形中的连通区域个数。
思路是把每个1*1方格拆分成3*3方格，再常规dfs即可。
一图胜千言。
代码
class Solution(object):
def regionsBySlashes(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
N = len(grid)
N3 = N * 3
traveled = [[False] * N3 for _ in range(N3)]
grid3 = [[0] * N3 for _ in range(N3)]
for i in range(N):
for j in range(N):
if grid[i][j] == '/':
grid3[i * 3][j * 3 + 2] = 1
grid3[i * 3 + 1][j * 3 + 1] = 1
grid3[i * 3 + 2][j * 3] = 1
elif grid[i][j] == "\\":
grid3[i * 3][j * 3] = 1
grid3[i * 3 + 1][j * 3 + 1] = 1
grid3[i * 3 + 2][j * 3 + 2] = 1
ret = 0
def dfs(i, j):
if i < 0 or i >= N3 or j < 0 or j >= N3:
return
if traveled[i][j] or grid3[i][j] == 1:
return
traveled[i][j] = True
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
for i in range(N3):
for j in range(N3):
if grid3[i][j] == 0 and not traveled[i][j]:
ret += 1
dfs(i, j)
return ret
AC，收工！
——此处是内容的分割线——
除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接
本文链接：https://www.utopiafar.com/2022/11/25/leetcode-959-regions-cut-by-slashes/
码字不易，如果觉得内容有帮助，欢迎留言or点赞！