130. Surrounded Regions (Medium)
https://leetcode.com/problems/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.
Solutions
class Solution {
public void solve(char[][] board) {
if (board == null || board.length <= 2 || board[0] == null || board[0].length <= 2) {
return;
}
int rows = board.length;
int cols = board[0].length;
// Any 'O' connected to a boundary can't be turned to 'X'
// Any 'O' connected to a boundary 'O' directly can't be turned
// Any 'O' connected to a boundary 'O' through other 'O' can't be turned
// Start from first and last column, turn 'O' to '*' and start infection
for (int i = 0; i < rows; i++) {
if (board[i][0] == 'O') {
infect(board, i, 0, rows, cols);
}
if (board[i][cols - 1] == 'O') {
infect(board, i, cols - 1, rows, cols);
}
}
// Start from first and last row, turn '0' to '*' and start infection
for (int j = 0; j < cols; j++) {
if (board[0][j] == 'O') {
infect(board, 0, j, rows, cols);
}
if (board[rows - 1][j] == 'O') {
infect(board, rows - 1, j, rows, cols);
}
}
// post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}
// Use DFS to turn internal however boundary-connected 'O' to '*';
private void infect(char[][] board, int i, int j, int rows, int cols) {
// Out of the boundary
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return;
}
// Not infectable or already infected.
if (board[i][j] != 'O') {
return;
}
board[i][j] = '*'; // Mark the connected cell with '*'.
// infect cells in four directions
infect(board, i + 1, j, rows, cols);
infect(board, i - 1, j, rows, cols);
infect(board, i, j + 1, rows, cols);
infect(board, i, j - 1, rows, cols);
}
}