Explore a diverse range of topics and get answers from knowledgeable individuals on IDNLearn.com. Get step-by-step guidance for all your technical questions from our dedicated community members.
/*
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For 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
*/
public class Solution {
// This algorithm cannot solve the large test set
public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
int rows = board.length;
if(rows == 0) return;
int cols = board[0].length;
for(int i = 0; i < cols; i++) {
// check first row's O
if(board[0][i] == 'O') {
// change it to other symbol
board[0][i] = '#';
dfs(board, 0, i);
}
// check the last row
if(board[rows - 1][i] == 'O') {
board[rows - 1][i] = '#';
dfs(board, rows - 1, i);
}
}
for(int i = 0; i < rows; i++) {
// check first col
if(board[i][0] == 'O') {
board[i][0] = '#';
dfs(board, i, 0);
}
// check last col
if(board[i][cols - 1] == 'O') {
board[i][cols - 1] = '#';
dfs(board, i, cols - 1);
}
}
// change O to X
changeTo(board, 'O', 'X');
// change # to O
changeTo(board, '#', 'O');
return;
}
public void dfs(char[][] board, int row, int col) {
// check up
if(row > 0) {
if(board[row - 1][col] == 'O') {
board[row - 1][col] = '#';
dfs(board, row - 1, col);
}
}
// check left
if(col > 0) {
if(board[row][col - 1] == 'O') {
board[row][col - 1] = '#';
dfs(board, row, col - 1);
}
}
// check right
if(row < board.length - 1) {
if(board[row + 1][col] == 'O') {
board[row+1][col] = '#';
dfs(board, row+1, col);
}
}
// check down
if(col < board[0].length - 1) {
if(board[row][col+1] == 'O'){
board[row][col+1] = '#';
dfs(board, row, col+1);
}
}
return;
}
public void changeTo(char[][] board, char from, char to) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == from) {
board[i][j] = to;
}
}
}
return;
}
}
We appreciate every question and answer you provide. Keep engaging and finding the best solutions. This community is the perfect place to learn and grow together. IDNLearn.com is your source for precise answers. Thank you for visiting, and we look forward to helping you again soon.