Surrounded Regions

LeetCode Q 130 - Surrounded Regions

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.

Solution

Solution : DFS

Code:

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public void solve(char[][] board) {
	if (board == null || board.length == 0 || board[0].length == 0)
		return;

	int R = board.length, C = board[0].length;
	
	for (int r = 0; r < R; r++) {
		if (board[r][0] == 'O') dfs(board, r, 0);
		if (board[r][C - 1] == 'O') dfs(board, r, C - 1);
	}

	for (int c = 0; c < C; c++) {
		if (board[0][c] == 'O') dfs(board, 0, c);
		if (board[R - 1][c] == 'O') dfs(board, R - 1, c);
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'U') board[r][c] = 'O';
			if (board[r][c] == 'O') board[r][c] = 'X';
		}
	}

	return;
}

private void dfs (char[][] board, int r, int c) {
	if (r < 0 || c < 0 || r == board.length || c == board[0].length || board[r][c] != 'O') 
		return;

	board[r][c] = 'U';

	for (int i = 0; i < 4; i++) {
		int nr = r + DIRS[i], nc = c + DIRS[i + 1];
		dfs(board, nr, nc);
	}

	return;
}

Solution : Disjoint Set / Union Find

Tips:

1. we’d better write the find function in the UnionFindSet iteratively to avoid Stack Overflow.
2. when making the union, let the one with bigger index be the root, making sure the Os on the borders has root R * C.

Code:

class UnionFindSet {
	int[] parent;
	public UnionFindSet (int size) {
		this.parent = new int[size];
		for (int i = 0; i < size; i++)
			parent[i] = i;
	}
	public int find (int x) {
		int p = x;
		while (p != parent[p]) 
			p = parent[p];
		return p;
	}
	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) parent[Math.min(px, py)] = Math.max(px, py);
	}
}
private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public void solve(char[][] board) {
	if (board == null || board.length == 0 || board[0].length == 0)
		return;

	int R = board.length, C = board[0].length;

	UnionFindSet ufs = new UnionFindSet(R * C + 1);

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'X') continue;
			if (r == 0 || r == R - 1 || c == 0 || c == C - 1) {
				ufs.union(r * C + c, R * C);
			} else {
				for (int i = 0; i < 4; i++) {
					int nr = r + DIRS[i], nc = c + DIRS[i + 1];
					if (board[nr][nc] == 'O')
						ufs.union(r * C + c, nr * C + nc);
				}
			}
		}
	}
	
	for (int r = 1; r < R - 1; r++) {
		for (int c = 1; c < C - 1; c++) {
			if (board[r][c] == 'O' && ufs.find(r * C + c) != R * C) 
				board[r][c] == 'X';
		}
	}

	return;
}