Given a 2D board containing 'X' and 'O' (the letter 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，刚开始用了HashSet<Integer>但是内存溢出了。
public class Solution {
public void solve(char[][] board) {
int row = board.length;
if( row < 2 )
return ;
int col = board[0].length;
if( col < 2 )
return ;
for( int i = 0;i<row;i++){
for( int j = 0;j<col;j++){
if( board[i][j] == 'O'){
HashSet<Integer> set = new HashSet<Integer>();
if( helper(board,i,j,set,false) ){
helpset('o',set,board);
}else
helpset('X',set,board);
}
}
}
for( int i = 0;i<row;i++){
for( int j = 0;j< col;j++){
if( board[i][j] == 'o')
board[i][j] = 'O';
}
}
}
public void helpset(char ch ,HashSet<Integer> set ,char[][] board){
for( int i : set ){
int row = i/board[0].length;
int col = i%board[0].length;
board[row][col] = ch;
}
}
public boolean helper(char[][] board,int num1, int num2,HashSet<Integer> set,boolean flag){
boolean result = flag;
if( num1-1 >= 0 && board[num1-1][num2] == 'O'){
int num = (num1-1)*board[0].length+num2;
if( !set.contains(num) ){
set.add(num);
result = result || helper(board,num1-1,num2,set,flag);
}
}
if( num1+1 < board.length && board[num1+1][num2] == 'O'){
int num = (num1+1)*board[0].length+num2;
if( !set.contains(num) ){
set.add(num);
result = result || helper(board,num1+1,num2,set,flag);
}
}
if( num2-1 >= 0 && board[num1][num2-1] == 'O'){
int num = num1*board[0].length+num2-1;
if( !set.contains(num) ){
set.add(num);
result = result || helper(board,num1,num2-1,set,flag);
}
}
if( num2+1 < board[0].length && board[num1][num2+1] == 'O'){
int num = num1*board[0].length+num2+1;
if( !set.contains(num) ){
set.add(num);
result = result || helper(board,num1,num2+1,set,flag);
}
}
if( num1 == 0 || num1 == board.length-1 || num2 == 0 || num2 == board[0].length-1)
return true;
return result;
}
}
2、换用思路，先把所有的O放入一个set中，然后在这个set中进行判断，虽然ac但是还是耗时还是较长。
public class Solution {
public void solve(char[][] board) {
int row = board.length;
if( row < 2 )
return ;
int col = board[0].length;
if( col < 2 )
return ;
HashSet<Integer> set = new HashSet<Integer>();
for( int i = 0;i<row;i++){
for( int j = 0;j<col;j++){
if( board[i][j] == 'O')
set.add(i*board[0].length+j);
}
}
while( !set.isEmpty() ){
helper(set,col,row,board);
}
return ;
}
public void helper(HashSet<Integer> set,int len,int row,char[][] board){
boolean result = false;
Queue<Integer> queue = new LinkedList<Integer>();
int[] set2 = new int[set.size()];
int num = set.iterator().next();
set2[0] = num;
int i = 1;
queue.add(num);
set.remove(num);
if (num % len == 0 || num % len == len - 1 || num / len == 0 || num / len == row - 1)
result = true;
while( !queue.isEmpty() ){
num = (Integer) queue.poll();
if( set.contains(num+1) ){
set2[i] = num+1;
i++;
queue.add(num+1);
set.remove(num+1);
if ((num+1) % len == 0 || (num+1) % len == len - 1 || (num+1) / len == 0 || (num+1) / len == row - 1)
result = true;
}
if( set.contains(num-1)){
set2[i] = (num-1);
i++;
queue.add(num-1);
set.remove(num-1);
if ((num-1) % len == 0 ||( num-1) % len == len - 1 || (num-1) / len == 0 || (num-1) / len == row - 1)
result = true;
}
if( set.contains(num+len) ){
set2[i] = (num+len);
i++;
queue.add(num+len);
set.remove(num+len);
if ((num+len) % len == 0 || (num+len )% len == len - 1 || (num+len) / len == 0 || (num+len) / len == row - 1)
result = true;
}
if( set.contains(num-len) ){
set2[i] = (num-len);
i++;
queue.add(num-len);
set.remove(num-len);
if ((num-len) % len == 0 || (num-len) % len == len - 1 || (num-len) / len == 0 || (num-len) / len == row - 1)
result = true;
}
}
if( result == true )
return ;
else
helpset('X',set2,i,board);
}
public void helpset(char ch ,int[] set,int num ,char[][] board){
for( int i = 0;i<num;i++){
int row = set[i]/board[0].length;
int col = set[i]%board[0].length;
board[row][col] = ch;
}
}
}
3、使用BFS和队列。
public class Solution {
public void solve(char[][] board) {
int row = board.length;
if( row < 2 )
return ;
int col = board[0].length;
if( col < 2 )
return ;
Queue<Integer> queue = new LinkedList<Integer>();
for( int i = 0;i<col;i++){
if( board[0][i] == 'O' )
queue.add(i);
if( board[row-1][i] == 'O')
queue.add((row-1)*col+i);
}
for( int i = 0;i < row ;i++){
if( board[i][col-1] == 'O')
queue.add(i*col+col-1);
if( board[i][0] == 'O')
queue.add(i*col);
}
while( !queue.isEmpty() ){
int num = queue.poll();
int x = num/col,y = num%col;
if( board[x][y] != 'O')
continue;
board[x][y] = 'o';
if( x-1>=0 && board[x-1][y] == 'O')
queue.add(num-col);
if( x+1<row && board[x+1][y] == 'O')
queue.add(num+col);
if( y-1>=0 && board[x][y-1] == 'O')
queue.add(num-1);
if( y+1<col && board[x][y+1] == 'O')
queue.add(num+1);
}
for( int i = 0;i<row;i++){
for( int j = 0;j<col;j++){
if( board[i][j] == 'O')
board[i][j] = 'X';
else if( board[i][j] == 'o')
board[i][j] = 'O';
}
}
return ;
}
}
4、不使用队列，直接用BFS。
public class Solution {
public void solve(char[][] board) {
if (board.length == 0) return;
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O')
dfs(board, i, 0);
if (board[i][col-1] == 'O')
dfs(board, i, col-1);
}
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O')
dfs(board, 0, i);
if (board[row - 1][i] == 'O')
dfs(board,row-1, i);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '1') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
return;
}
public void dfs(char[][] board, int m, int n) {
if (board[m][n] != 'O') return;
board[m][n] = '1';
if (m < board.length - 2)
dfs(board, m + 1, n);
if (m > 1)
dfs(board, m - 1, n);
if (n < board[0].length - 2)
dfs(board, m, n + 1);
if (n > 1)
dfs(board, m, n - 1);
}
}