# 959. Regions Cut By Slashes

## 题目

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，非常有意思的一道题。

## 代码

``````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 = [ * 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，收工！

——此处是内容的分割线——