959. Regions Cut By Slashes #

题目 #

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 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。(请注意，反斜杠字符是转义的，因此 \ 用 “\” 表示)返回区域的数目。

提示：

1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 ‘/'、''、或 ' ‘。

解题思路 #

给出一个字符串，代表的是 N x N 正方形中切分的情况，有 2 种切分的情况 '\' 和 '/' ，即从左上往右下切和从右上往左下切。问按照给出的切分方法，能把 N x N 正方形切成几部分？
这一题解题思路是并查集。先将每个 1*1 的正方形切分成下图的样子。分成 4 小块。然后按照题目给的切分图来合并各个小块。

遇到 '\\'，就把第 0 块和第 1 块 union() 起来，第 2 块和第 3 块 union() 起来；遇到 '/'，就把第 0 块和第 3 块 union() 起来，第 2 块和第 1 块 union() 起来；遇到 ' '，就把第 0 块和第 1 块 union() 起来，第 2 块和第 1 块 union() 起来，第 2 块和第 3 块 union() 起来，即 4 块都 union() 起来；最后还需要记得上一行和下一行还需要 union()，即本行的第 2 块和下一行的第 0 块 union() 起来；左边一列和右边一列也需要 union()。即本列的第 1 块和右边一列的第 3 块 union() 起来。最后计算出集合总个数就是最终答案了。

代码 #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func regionsBySlashes(grid []string) int {
	size := len(grid)
	uf := template.UnionFind{}
	uf.Init(4 * size * size)
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			switch grid[i][j] {
			case '\\':
				uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1))
				uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3))
			case '/':
				uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 3))
				uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1))
			case ' ':
				uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1))
				uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1))
				uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3))
			}
			if i < size-1 {
				uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i+1, j, 0))
			}
			if j < size-1 {
				uf.Union(getFaceIdx(size, i, j, 1), getFaceIdx(size, i, j+1, 3))
			}
		}
	}
	count := 0
	for i := 0; i < 4*size*size; i++ {
		if uf.Find(i) == i {
			count++
		}
	}
	return count
}

func getFaceIdx(size, i, j, k int) int {
	return 4*(i*size+j) + k
}

⬅️上一页

下一页➡️