130. Surrounded Regions #

Problem #

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Problem Summary #

Given a two-dimensional matrix containing ‘X’ and ‘O’ (the letter O). Find all regions surrounded by ‘X’, and fill all ‘O’s in these regions with ‘X’. Surrounded regions will not exist on the border; in other words, any ‘O’ on the border will not be filled as ‘X’. Any ‘O’ that is not on the border, or is not connected to an ‘O’ on the border, will eventually be filled as ‘X’. If two elements are adjacent horizontally or vertically, they are considered “connected”.

Solution Ideas #

• Given a two-dimensional map, cover all ‘O’s on the map that are not on the edge with ‘X’.
• There are multiple solutions to this problem. The first solution is Union-Find. First, union() all ‘O’s on the edge with a special point. Then union() all ‘O’s in the middle of the map, and finally mark all points that are not in the same set as the special point as ‘X’. The second solution is DFS or BFS. You can first mark the ‘O’s on the edge as another character, and then during the recursive traversal, mark all remaining ‘O’s as ‘X’.

Code #

package leetcode

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

// Solution 1: Union-Find
func solve(board [][]byte) {
	if len(board) == 0 {
		return
	}
	m, n := len(board[0]), len(board)
	uf := template.UnionFind{}
	uf.Init(n*m + 1) // Intentionally add one extra special point for marking

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if (i == 0 || i == n-1 || j == 0 || j == m-1) && board[i][j] == 'O' { // 'O' cells on the board border
				uf.Union(i*m+j, n*m)
			} else if board[i][j] == 'O' { // Internal 'O' cells not on the board border
				if board[i-1][j] == 'O' {
					uf.Union(i*m+j, (i-1)*m+j)
				}
				if board[i+1][j] == 'O' {
					uf.Union(i*m+j, (i+1)*m+j)
				}
				if board[i][j-1] == 'O' {
					uf.Union(i*m+j, i*m+j-1)
				}
				if board[i][j+1] == 'O' {
					uf.Union(i*m+j, i*m+j+1)
				}

			}
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if uf.Find(i*m+j) != uf.Find(n*m) {
				board[i][j] = 'X'
			}
		}
	}
}

// Solution 2: DFS
func solve1(board [][]byte) {
	for i := range board {
		for j := range board[i] {
			if i == 0 || i == len(board)-1 || j == 0 || j == len(board[i])-1 {
				if board[i][j] == 'O' {
					dfs130(i, j, board)
				}
			}
		}
	}

	for i := range board {
		for j := range board[i] {
			if board[i][j] == '*' {
				board[i][j] = 'O'
			} else if board[i][j] == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}

func dfs130(i, j int, board [][]byte) {
	if i < 0 || i > len(board)-1 || j < 0 || j > len(board[i])-1 {
		return
	}
	if board[i][j] == 'O' {
		board[i][j] = '*'
		for k := 0; k < 4; k++ {
			dfs130(i+dir[k][0], j+dir[k][1], board)
		}
	}
}