# Java BFS&Union-Find solution. Straight forward.

But I'm using BFS to avoid potential stack overflow when using DFS.

``````public class Solution {
// Define Node class to store position information.
// Each element in board can be regarded as a Node, since we are using BFS
// x is row index and y is column index
class Node {
int x;
int y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}

public void solve(char[][] board) {
// When board is smaller than or equal to 2*2. No change needed. Return.
if (board == null || board.length < 3 || board[0].length < 3) {
return;
}

int m = board.length;
int n = board[0].length;

// Use array visited to avoid re-visited, which will cause infinite loop
int[][] visited = new int[m][n];

// This is the first "layer" of Nodes
// They are 'O' Nodes at the boundary
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
queue.offer(new Node(i, 0));
}
if (board[i][n - 1] == 'O') {
queue.offer(new Node(i, n - 1));
}
}

for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
queue.offer(new Node(0, i));
}
if (board[m - 1][i] == 'O') {
queue.offer(new Node(m - 1, i));
}
}

// BFS use queue
// iterate the current "layer" and put next "layer" into the queue
// The next "layer" are those unvisited 'O' Nodes that are adjacent to current Nodes
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
update(node, visited, queue, board);
}
}

// Traverse the board. Change 'O' Node to 'X', '*' Node to 'O'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}

// Change the character at this position to '*' and mark as visited
// Put adjacent, unvisited, 'O' Node to the queue. They are the next "layer"
public void update(Node node, int[][] visited, Queue<Node> queue, char[][] board) {
board[node.x][node.y] = '*';
visited[node.x][node.y] = 1;

if (node.x - 1 >= 0 && visited[node.x - 1][node.y] == 0 && board[node.x - 1][node.y] == 'O') {
queue.offer(new Node(node.x - 1, node.y));
}
if (node.x + 1 < board.length && visited[node.x + 1][node.y] == 0 && board[node.x + 1][node.y] == 'O') {
queue.offer(new Node(node.x + 1, node.y));
}
if (node.y - 1 >= 0 && visited[node.x][node.y - 1] == 0 && board[node.x][node.y - 1] == 'O') {
queue.offer(new Node(node.x, node.y - 1));
}
if (node.y + 1 < board[0].length && visited[node.x][node.y + 1] == 0 && board[node.x][node.y + 1] == 'O') {
queue.offer(new Node(node.x, node.y + 1));
}
}
}
``````

Another solution is to use Union-Find like this:

``````public class Solution {
class UF {
public int count;
public int[] id;

UF (int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}

public int find(int p) {
while (p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
id[pRoot] = qRoot;
return;
}

public boolean isConnected(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return true;
} else {
return false;
}
}
}

public void solve(char[][] board) {
if (board == null || board.length < 3 || board[0].length < 3) {
return;
}

int m = board.length;
int n = board[0].length;
UF uf = new UF(m * n + 1);  //an extra node is created as dummy node

// Union all 'O' at boundary to the dummy node and union all 'O' nodes
// In this situation, all the 'O' node that are connected to the boundary 'O' node are connected to the dummy node
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1)) {
uf.union(i * n + j, m * n);
} else if (board[i][j] == 'O') {
// check and connect with neighbor 'O' nodes
if (i > 0 && board[i - 1][j] == 'O') {
uf.union((i - 1) * n + j, i * n + j);
}
if (i < m - 1 && board[i + 1][j] == 'O') {
uf.union((i + 1) * n + j, i * n + j);
}
if (j > 0 && board[i][j - 1] == 'O') {
uf.union(i * n + j - 1, i * n + j);
}
if (j < n - 1 && board[i][j + 1] == 'O') {
uf.union(i * n + j + 1, i * n + j);
}
}
}
}

// traverse the board to mark all the 'O' that is not connected to the dummy node
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && !uf.isConnected(i * n + j, m * n)) {
board[i][j] = 'X';
}
}
}
}
}
``````

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