130. Surrounded Regions

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

Similar:

286. Walls and Gates
200. Number of Islands

 1 public class Solution {
 2     public void solve(char[][] board) {
 3         if (board.length == 0 || board[0].length == 0)
 4             return;
 5         int m = board.length;
 6         int n = board[0].length;
 7         
 8         Queue<int[]> queue = new LinkedList<int[]>();
 9         for (int i = 0; i < m; i++) {
10             if (board[i][0] == 'O') {
11                 board[i][0] = 'H';
12                 queue.offer(new int[] {i,0});
13             }
14             if (board[i][n-1] == 'O') {
15                 board[i][n-1] = 'H';
16                 queue.offer(new int[] {i,n-1});
17             }
18         }
19         for (int j = 1; j < n-1; j++) {
20             if (board[0][j] == 'O') {
21                 board[0][j] = 'H';
22                 queue.offer(new int[] {0,j});
23             }
24             if (board[m-1][j] == 'O') {
25                 board[m-1][j] = 'H';
26                 queue.offer(new int[] {m-1,j});
27             }
28         }
29         
30         int[] shift = {1, 0, -1, 0, 1};
31         while (!queue.isEmpty()) {
32             int[] pt = queue.poll();
33             for (int i=0; i<4; i++) {
34                 int r = pt[0] + shift[i];
35                 int c = pt[1] + shift[i+1];
36                 if (r>=0 && r<m && c>=0 && c<n && board[r][c]=='O') {
37                     board[r][c] = 'H';
38                     queue.offer( new int[] {r,c});
39                 }
40             }
41         }
42         
43         for (int i=0; i<m; i++)
44             for (int j=0; j<n ;j++) {
45                 if (board[i][j] =='O') {
46                     board[i][j] = 'X';
47                 }
48             }
49         for (int i=0; i<m; i++)
50             for (int j=0; j<n; j++) {
51                 if (board[i][j] == 'H') {
52                     board[i][j] = 'O';
53                 }
54             }
55     }
56 }