首页 > 代码库 > Problem Surrounded Regions
Problem Surrounded Regions
Problem Description:
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
Solution:
1 public void solve(char[][] board) { 2 Stack<Integer> sx = new Stack<Integer>(); 3 Stack<Integer> sy = new Stack<Integer>(); 4 5 if (board == null || board.length == 0) return; 6 if (board[0].length == 0) return; 7 8 int row = board.length; 9 int col = board[0].length;10 11 for (int i = 0; i < row; i++) {12 if (board[i][0] == ‘O‘) {13 sx.push(i);14 sy.push(0);15 }16 17 if (board[i][col - 1] == ‘O‘) {18 sx.push(i);19 sy.push(col - 1);20 }21 }22 23 for (int j = 0; j < col; j++) {24 if (board[0][j] == ‘O‘) {25 sx.push(0);26 sy.push(j);27 }28 29 if (board[row - 1][j] == ‘O‘) {30 sx.push(row - 1);31 sy.push(j);32 }33 }34 while (! sx.isEmpty()) {35 int x = sx.pop();36 int y = sy.pop();37 38 board[x][y] = ‘#‘;39 40 if (y > 0 && board[x][y - 1] == ‘O‘) {41 sx.push(x);42 sy.push(y - 1);43 }44 45 if (y < col - 1 && board[x][y + 1] == ‘O‘) {46 sx.push(x);47 sy.push(y + 1);48 }49 50 if (x > 0 && board[x - 1][y] == ‘O‘) {51 sx.push(x - 1);52 sy.push(y);53 }54 if (x < row - 1 && board[x + 1][y] == ‘O‘) {55 sx.push(x + 1);56 sy.push(y);57 }58 59 }60 for (int i = 0; i < row; i++) 61 for (int j = 0; j < col; j++) {62 if (board[i][j] == ‘#‘) {63 board[i][j]= ‘O‘;64 } else {65 board[i][j] = ‘X‘;66 }67 }68 69 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。