959. Regions Cut By Slashes

959. Regions Cut By Slashes

难度: Medium

刷题内容

原题连接

内容描述

In 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:



Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

解题方案

思路 1
*- 时间复杂度: O(row * col)- 空间复杂度: O(row * col)*

看成一个大图,每个格子有4个方位,上下左右,根据格子里的内容是'\\', '/'还是' '来连接每个格子的不同方位

  • 格子里的内容是'\\', 那么当前格子的上和右肯定连接起来,下和左肯定连接起来
  • 格子里的内容是'/', 那么当前格子的上和左肯定连接起来,下和右肯定连接起来
  • 格子里的内容是' ', 那么当前格子的上下左右全部连接起来
  • 每个格子的上和它上面那个格子(如果存在)的下肯定连接起来
  • 每个格子的下和它下面那个格子(如果存在)的上肯定连接起来
top Created with Sketch.