[leetcode]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

算法思路：由外向内扫描，因为边界的O肯定是escape的，这样由边界往里面纵深查找出没有被capture的O

思路1：dfs，第一次居然过了，然后就再也过不去了，试想一个矩阵是100* 100并且全是O，如果dfs的话，就会有10000层，栈空间都溢出了....

思路2：BFS，大数据无压力过

代码如下：

 1 public class Solution {
 2 public void solve(char[][] board) {
 3         if(board == null || board.length == 0 ) return;
 4         int height = board.length;
 5         int width = board[0].length;
 6         int code = Math.max(height, width);
 7         for(int i = 0; i < height; i++){
 8             for(int j = 0; j < width; j++){
 9                 if(board[i][j] == 'O' && (i == 0 || i == height - 1 || j == 0 || j == width - 1)){
10                     board[i][j] = '@';
11                     bfs(board, height, width, i, j, code);
12                 }
13             }
14         }
15         for(int i = 0; i < height; i++){
16             for(int j = 0; j < width; j++){
17                 if(board[i][j] == 'O'){
18                     board[i][j] = 'X';
19                 }else if(board[i][j] == '@'){
20                     board[i][j] = 'O';
21                 }
22             }
23         }
24     }
25     int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
26     private void bfs(char[][] board,int height,int width,int i ,int j,int code){
27         Queue<Integer> q = new LinkedList<Integer>();
28         q.offer(i * code + j);//将二维下标压缩成一维，方便存储
29         while(!q.isEmpty()){
30             int tem = q.poll();
31             int row = tem / code;
32             int col = tem % code;
33             for(int k = 0;k < dir.length; k++){
34                 if(row + dir[k][0] < height && row + dir[k][0] >= 0 && col + dir[k][1] < width && col + dir[k][1] >= 0){
35                     if(board[row + dir[k][0]][col + dir[k][1]] == 'O'){
36                         board[row + dir[k][0]][col + dir[k][1]] = '@';
37                         q.offer((row + dir[k][0]) * code + col + dir[k][1]);
38                     }
39                 }
40             }
41         }
42     }
43 }

坐标压缩法很有意思。