# My concise JAVA solution based on BFS

• Explanation

The basic idea is to find all O connecting to 4 borders, then flip the left O into X.

For this problem, stack will overflow if we use DFS, because DFS method just pushes nodes to stack till meets the leaf, and then processes from the leaf backtracking to the root. If the path from root to leaf is too long, it will cause stack overflow. So I adopt BFS to solve this problem, as the following:

``````public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int n = board.length, m = board[0].length;

for (int i = 0; i < n; i++) {
check(board, i, 0);
check(board, i, m - 1);
}

for (int j = 0; j < m; j++) {
check(board, 0, j);
check(board, n - 1, j);
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'V' || board[i][j] == 'O') // V means visited
board[i][j] = 'X';
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == '1') // 1 means O at the border
board[i][j] = 'O';
}
}
}

// BFS
void check(char[][] vec,int i, int j){
queue.offer(new Point(i, j));

do {
Point point = queue.poll();
int x = point.x, y = point.y;
if(vec[x][y]=='1' || vec[x][y]=='V') // 1 means O at the border; V means visited
continue;

if(vec[x][y]=='O'){
vec[x][y]='1';
if(x - 1 >= 0)
queue.offer(new Point(x-1,y));
if(y - 1 >= 0)
queue.offer(new Point(x,y-1));
if(x + 1 < vec.length)
queue.offer(new Point(x+1,y));
if(y + 1 < vec[0].length)
queue.offer(new Point(x,y+1));
} else {
vec[x][y]='V'; //Set visited
}
} while (!queue.isEmpty());
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.