2014年4月25日 星期五

[LeetCode] Surrounded Regions

Problem:
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 X
Solution: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';
         }
      }      
   }
}

沒有留言:

張貼留言