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


从四个边入手，把不能换成X的O标记出来，用map存。 然后再遍历这个array， 更改可以变成X的。

 1 public class Solution {
 2     public void solve(char[][] board) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         if(board == null || board.length == 0 || board[0].length == 0) return;
 6         boolean[][] map = new boolean[board.length][board[0].length];
 7         int len = board[0].length;
 8         LinkedList<Integer> ll = new LinkedList<Integer>();
 9         for(int i = 0; i < board.length; i ++){
10             if(board[i][0] == 'O' && !map[i][0]){
11                 map[i][0] = true;
12                 ll.push(i * len);
13             } 
14             if(board[i][len - 1] == 'O' && !map[i][len - 1]){ 
15                 map[i][len - 1] = true;
16                 ll.push(i * len + len - 1);
17             }
18         }
19         for(int i = 0; i < len; i ++){
20             if(board[0][i] == 'O' && !map[0][i]){
21                 map[0][i] = true;
22                 ll.push(i);
23             } 
24             if(board[board.length - 1][i] == 'O' && !map[board.length - 1][i]){ 
25                 map[board.length - 1][i] = true;
26                 ll.push((board.length - 1) * len + i);
27             }
28         }
29         while(ll.size() != 0){
30             int tmp = ll.poll();
31             int i = tmp / len;
32             int j = tmp % len;
33             if(i > 1 && board[i - 1][j] == 'O' && !map[i - 1][j]){
34                 map[i - 1][j] = true;
35                 ll.push((i - 1) * len + j);
36             }
37             if(j > 1 && board[i][j - 1] == 'O' && !map[i][j - 1]){
38                 map[i][j - 1] = true;
39                 ll.push(i * len + j - 1);
40             }
41             if(i + 1 < board.length && board[i + 1][j] == 'O' && !map[i + 1][j]){
42                 map[i + 1][j] = true;
43                 ll.push((i + 1) * len + j);
44             }
45             if(j + 1 < len && board[i][j + 1] == 'O' && !map[i][j + 1]){
46                 map[i][j + 1] = true;
47                 ll.push(i * len + j + 1);
48             }
49         }
50         for(int i = 0; i < board.length; i ++)
51             for(int j = 0; j < len; j ++)
52                 if(!map[i][j] && board[i][j] == 'O')
53                     board[i][j] = 'X';
54     }
55 }