# BFS-based solution in Java

• ``````/*
dfs, bfs, union-find都可以做, 基本思路是
从在四个边的各个'O'开始搜索, 连在一起的'O'就是不能被包围的, 其余的点都应该设为'X'.

如果选择bfs, 可以把所有边上的所有'O'一起入队, 同时进行bfs
*/
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return;
int height = board.length, width = board[0].length;
Deque<int[]> queue = new ArrayDeque<>();  // int[2] as [row, col]
for (int i = 0; i < width; ++i) {
if (board[0][i] == 'O') {
board[0][i] = 'V';  // mark as visited
}
if (board[height - 1][i] == 'O') {
queue.addLast(new int[] {height - 1, i});
board[height - 1][i] = 'V';
}
}
for (int i = 1; i < height - 1; ++i) {
if (board[i][0] == 'O') {
board[i][0] = 'V';
}
if (board[i][width - 1] == 'O') {
queue.addLast(new int[] {i, width - 1});
board[i][width - 1] = 'V';
}
}
while (!queue.isEmpty()) {
int[] cur = queue.removeFirst();
if (cur[0] - 1 >= 0 && board[cur[0] - 1][cur[1]] == 'O') {  // up
queue.addLast(new int[] {cur[0] - 1, cur[1]});
board[cur[0] - 1][cur[1]] = 'V';
}
if (cur[0] + 1 < height && board[cur[0] + 1][cur[1]] == 'O') {  // down
queue.addLast(new int[] {cur[0] + 1, cur[1]});
board[cur[0] + 1][cur[1]] = 'V';
}
if (cur[1] - 1 >= 0 && board[cur[0]][cur[1] - 1] == 'O') {  // left
queue.addLast(new int[] {cur[0], cur[1] - 1});
board[cur[0]][cur[1] - 1] = 'V';
}
if (cur[1] + 1 < width && board[cur[0]][cur[1] + 1] == 'O') {  // right
queue.addLast(new int[] {cur[0], cur[1] + 1});
board[cur[0]][cur[1] + 1] = 'V';
}
}
for (int i = 0; i < height; ++i) {
for (int j = 0; j < width; ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == 'V') board[i][j] = 'O';
}
}
}
}``````

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