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.
class Solution {
int directions[][] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
public void solve(char[][] board) {
int m = board.length;
if (m == 0)
return;
int n = board[0].length;
boolean visited[][] = new boolean[m][n];
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
marker(board, visited, 0, j);
if (board[m - 1][j] == 'O')
marker(board, visited, m - 1, j);
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O')
marker(board, visited, i, 0);
if (board[i][n - 1] == 'O')
marker(board, visited, i, n - 1);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (!visited[i][j])
board[i][j] = 'X';
}
public void marker(char[][] grid, boolean[][] visited, int x, int y) {
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && !visited[x][y] && grid[x][y] == 'O') {
visited[x][y] = true;
for (int i = 0; i < 4; i++)
marker(grid, visited, x + directions[i][0], y + directions[i][1]);
}
}
}
Last updated