959. Regions Cut By Slashes #

Problem #

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 ' '.

Problem Summary #

In an N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of /, , or a blank space. These characters divide the squares into regions sharing edges. (Note that backslash characters are escaped, so \ is represented as “\") Return the number of regions.

Hints:

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

Solution Ideas #

Given a string representing the cutting situation in an N x N square, there are 2 types of cuts: '\' and '/', namely cutting from the upper left to the lower right and cutting from the upper right to the lower left. Ask how many parts the N x N square can be cut into according to the given cutting method.
The solution idea for this problem is Union Find. First split each 1*1 square into the form shown below. Divide it into 4 small pieces. Then merge each small piece according to the cutting diagram given in the problem.

When encountering '\\', union() block 0 with block 1, and union() block 2 with block 3; when encountering '/', union() block 0 with block 3, and union() block 2 with block 1; when encountering ' ', union() block 0 with block 1, union() block 2 with block 1, and union() block 2 with block 3, that is, union() all 4 blocks together; finally, remember that the previous row and the next row also need to be union()ed, that is, union() block 2 of the current row with block 0 of the next row; the left column and the right column also need to be union()ed. That is, union() block 1 of this column with block 3 of the column to the right. Finally, calculate the total number of sets, which is the final answer.

Code #


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
}