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.
Solution (Java)
class Solution {
public void solve(char[][] board) {
// Edge case, empty grid
if (board.length == 0) {
return;
}
// Traverse first and last rows ( boundaries)
for (int i = 0; i < board[0].length; i++) {
// first row
if (board[0][i] == 'O') {
// It will covert O and all it's touching O's to #
dfs(board, 0, i);
}
// last row
if (board[board.length - 1][i] == 'O') {
// Coverts O's to #'s (same thing as above)
dfs(board, board.length - 1, i);
}
}
// Traverse first and last Column (boundaries)
for (int i = 0; i < board.length; i++) {
// first Column
if (board[i][0] == 'O') {
// Converts O's to #'s
dfs(board, i, 0);
}
// last Column
if (board[i][board[0].length - 1] == 'O') {
// Coverts O's to #'s
dfs(board, i, board[0].length - 1);
}
}
// Traverse through entire matrix
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
// Convert O's to X's
board[i][j] = 'X';
}
if (board[i][j] == '#') {
// Convert #'s to O's
board[i][j] = 'O';
}
}
}
}
void dfs(char[][] board, int row, int column) {
if (row < 0
|| row >= board.length
|| column < 0
|| column >= board[0].length
|| board[row][column] != 'O') {
return;
}
board[row][column] = '#';
dfs(board, row + 1, column);
dfs(board, row - 1, column);
dfs(board, row, column + 1);
dfs(board, row, column - 1);
}
}
Solution (Javascript)
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
var xLen = board.length;
var yLen = (board[0] || []).length;
for (var i = 0; i < xLen; i++) {
dfs(board, i, 0, xLen, yLen);
dfs(board, i, yLen - 1, xLen, yLen);
}
for (var j = 0; j < yLen; j++) {
dfs(board, 0, j, xLen, yLen);
dfs(board, xLen - 1, j, xLen, yLen);
}
for (var m = 0; m < xLen; m++) {
for (var n = 0; n < yLen; n++) {
if (board[m][n] === '-') board[m][n] = 'O';
else if (board[m][n] === 'O') board[m][n] = 'X';
}
}
};
var dfs = function (board, x, y, xLen, yLen) {
if (x >= 0 && y >= 0 && x < xLen && y < yLen && board[x][y] === 'O') {
board[x][y] = '-';
dfs(board, x + 1, y, xLen, yLen);
dfs(board, x - 1, y, xLen, yLen);
dfs(board, x, y + 1, xLen, yLen);
dfs(board, x, y - 1, xLen, yLen);
}
};
Explain:
nope.
Complexity:
- Time complexity : O(m * n).
- Space complexity : O(1).