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 XSolution:O(m*n)
public class Solution { public void solve(char[][] board) { if(board == null || board.length ==0) return; boolean hasChange = true; while(hasChange){ hasChange = false; for(int i=0; i<board.length; i++){ for(int j=0; j<board[0].length;j++){ if(board[i][j] == 'A'){ if(i <board.length-1 && board[i+1][j] == 'S'){ board[i+1][j] = 'A'; hasChange = true; } if(j<board[0].length-1 && board[i][j+1] == 'S'){ board[i][j+1] = 'A'; hasChange = true; } } else if(board[i][j] == 'O'){ if(i == 0 || i == board.length -1 || j ==0 || j == board[0].length -1){ board[i][j] = 'A'; continue; } if(board[i-1][j] == 'A' || board[i][j-1] == 'A' || board[i+1][j] == 'A' || board[i][j+1] == 'A'){ board[i][j] = 'A'; hasChange = true; continue; } if(board[i-1][j] == 'X' && board[i][j-1] == 'X' && board[i+1][j] == 'X' && board[i][j+1] == 'X'){ board[i][j] = 'X'; hasChange = true; continue; } if(board[i+1][j] == 'O' || board[i][j+1] == 'O'){ board[i][j] = 'S'; hasChange = true; continue; } } else if(board[i][j] == 'S'){ if(board[i+1][j] == 'A' || board[i][j+1] == 'A' || board[i-1][j] == 'A' || board[i][j-1] == 'A'){ board[i][j] = 'A'; hasChange = true; continue; } } } } } for(int i=0; i<board.length; i++){ for(int j=0; j<board[0].length;j++){ if(board[i][j] == 'S' || board[i][j] == 'O') board[i][j] = 'X'; if(board[i][j] == 'A') board[i][j] = 'O'; } } } }
沒有留言:
張貼留言