首页 > 代码库 > Surrounded Regions

Surrounded Regions

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 XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

 1 import java.util.LinkedList; 2 import java.util.Queue; 3  4 public class Solution { 5     private char board[][]; 6     private int rows; 7     private int cols;                                                        //行和列数 8     private Queue<Integer> queue = new LinkedList<Integer>();                //BFS使用的队列 9     10     public void solve(char[][] board) {11         this.board = board;12         if(null == board || board.length == 0 || board[0].length == 0)        //特殊的直接返回13             return;14         rows = this.board.length;15         cols = this.board[0].length;                                        //获取行和列的数目16         17         for(int i = 0; i < rows; i++){18             traver(i, 0);                                                    //第一列19             traver(i, cols - 1);                                            //最后一列20         }21         for(int i = 0; i < cols; i++){22             traver(0, i);                                                    //第一行23             traver(rows - 1, i);                                            //最后一行24         }25         //遍历整个数组26         for(int i = 0; i < rows;i++){27             for(int j = 0; j < cols; j++){28                 board[i][j] = this.board[i][j] == ‘Z‘ ? ‘O‘ : ‘X‘;29             }30         }31     }32     33     /**34      * 对x,y所指的单元进行BFS35      * @param x36      * @param y37      */38     public void traver(int x, int y){39         add(x, y);40         while(!this.queue.isEmpty()){41             int head = queue.poll();                                        //出队列42             int temp_x = head / cols;43             int temp_y = head % cols;44             add(temp_x - 1, temp_y);45             add(temp_x + 1, temp_y);46             add(temp_x, temp_y - 1);47             add(temp_x, temp_y + 1);                                        //flood fill算法的体现48         }49     }50     51     /**52      * x,y所指的单元如果是‘o‘放到队列中,x * cols + y53      * @param x54      * @param y55      */56     public void add(int x, int y){57         if(x >= 0 && x < rows && y >= 0 && y < cols && this.board[x][y] == ‘O‘)58         {59             this.queue.add(x * cols + y);60             this.board[x][y] = ‘Z‘;61         }62     }63     64 }

BFS, FLOOD FILL...待续

参考:http://blog.csdn.net/pickless/article/details/12074363

Surrounded Regions