Leetcode --- Surrounded Regions(Medium)
===

## Description

Given an m x n matrix 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.

給一個二為陣列,其中只有'O'跟'X'字元,如果O被X包圍住則要翻牌為X,而邊界不算被包圍住.

### Examples

* **Ex1:**


**Input**: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
**Output**: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
**Explanation**: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

* **Ex2**:

**Input**: board = [["X"]]
**Output**: [["X"]]

### Constraints

* m == board.length
* n == board[i].length
* 1 <= m, n <= 200
* board[i][j] exactly is 'X' or 'O'.

## Solution

Two pass可行:
* Pass 1: 找出要留下的O
* Pass 2: 翻牌

如何找出要留下的O => 除非邊界有'O'且與邊界相鄰的'O'才能被留下來,所以可以依序尋找邊界的'O',若找到則往四面(上下左右)探索,直到四面都為X,則為欲被保留下的'O',剩下的都為'X'

翻牌 => 全部都給'X',除了被畫上記號者為'O'(欲被保留下者).

### Implement code (ver 1.)

class Solution {
    public void solve(char[][] board) {
        boolean[][] locker = new boolean[board.length][board[0].length];
        
        for(int y =0;y<board[0].length ; y++)
        {
            if(board[0][y] == 'O')
                explore(board,0,y,locker);
            if(board[board.length-1][y] == 'O')
                explore(board,board.length-1,y,locker);
        }
        for(int x =0;x<board.length ; x++)
        {
            if(board[x][0] == 'O')
                explore(board,x,0,locker);
            if(board[x][board[0].length-1] == 'O')
                explore(board,x,board[0].length-1,locker);
        } 
        
        for(int x =0 ;x< board.length ;x++)
            for(int y=0 ;y<board[0].length ; y++)
            {
                if(locker[x][y] ==true)
                    continue;
                board[x][y] ='X';
            }
    }
    private void explore(char[][] board,int x,int y,boolean[][] locker)
    {
        locker[x][y] =true;
        try
        {
            if(board[x][y+1] == 'O' && locker[x][y+1]==false)//right
                explore(board,x,y+1,locker); 
        } 
        catch(Exception e)
        {
            ;
        }
        
        try
        {
            if(board[x+1][y] == 'O'&& locker[x+1][y]==false)//down
                explore(board,x+1,y,locker);
        }   
        catch(Exception e)
        {
            ;
        }
        
        try
        {
            if(board[x][y-1] == 'O'&& locker[x][y-1]==false)//left
                explore(board,x,y-1,locker);
        }            
        catch(Exception e)
        {
            ;
        }
        
        try
        {
            if(board[x-1][y] == 'O'&& locker[x-1][y]==false)//up
                explore(board,x-1,y,locker);
        }            
        catch(Exception e)
        {
            ;
        }
    }
}

line 5~18 : 掃過邊界存在的'O' (Pass 1)
line 20~26 : 翻牌 (Pass 2)
Function **explore** :用來往四面探索,使用try catch將邊界問題的例外解決,簡單來說為DFS之概念.

#### Complexity Analysis
Pass2 欲掃過整張圖 =>
**O(nm)**
#### Submission on leecode

Runtime: **34 ms**, faster than **5.14%** of Java online submissions for Surrounded Regions.
Memory Usage: **39.4 MB, less than 99.95%** of Java online submissions for Surrounded Regions.

**Notice:**
==Question:== try ... catch 是否會**影響效能**?
==Answer==:try...catch只有在發生Exception時才會**嚴重危害效能**，平時正常執行時，我們倒可以"幾乎忘了它的存在"。

而以上code必定會掉入exception中,所以使效能降低

### Implement code (ver 2.)

class Solution {
    public void solve(char[][] board) {
        boolean[][] locker = new boolean[board.length][board[0].length];
        
        for(int y =0;y<board[0].length ; y++)
        {
            if(board[0][y] == 'O')
                explore(board,0,y,locker);
            if(board[board.length-1][y] == 'O')
                explore(board,board.length-1,y,locker);
        }
        for(int x =0;x<board.length ; x++)
        {
            if(board[x][0] == 'O')
                explore(board,x,0,locker);
            if(board[x][board[0].length-1] == 'O')
                explore(board,x,board[0].length-1,locker);
        }
           
        for(int x =0 ;x< board.length ;x++)
            for(int y=0 ;y<board[0].length ; y++)
            {
                if(locker[x][y] ==true)
                    continue;
                board[x][y] ='X';
            }
                
    }
    private void explore(char[][] board,int x,int y,boolean[][] locker)
    {
        if(x<0 || y<0 || x> board.length-1 || y > board[0].length-1 || locker[x][y])
            return;
        
        locker[x][y] =true;
        if(board[x][y] == 'O')
        {
            explore(board,x,y+1,locker); 
            explore(board,x+1,y,locker);
            explore(board,x,y-1,locker);
            explore(board,x-1,y,locker);
        }
    }
}

line 31: 將所有條件濃縮成一個判斷式,避免掉發生exception的情況.

#### Submission on leecode

Runtime: **1 ms, faster than 99.47%** of Java online submissions for Surrounded Regions.
Memory Usage: **40.9 MB, less than 67.71%** of Java online submissions for Surrounded Regions.

###### tags: `Leetcode` `Medium` `DFS`