Join IDNLearn.com and start getting the answers you've been searching for. Discover prompt and accurate responses from our experts, ensuring you get the information you need quickly.
/*
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 value your participation in this forum. Keep exploring, asking questions, and sharing your insights with the community. Together, we can find the best solutions. Find reliable answers at IDNLearn.com. Thanks for stopping by, and come back for more trustworthy solutions.