题目
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].length
1 <= n <= 30
grid[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点赞!