首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。