LeetCode - 130. Surrounded Regions

Category: Algorithm
Difficulty: Medium
Tags: Breadth-first Search, Union Find
Discription: https://leetcode.com/problems/surrounded-regions/#/description

題目會給一個標記為O與X的二維陣列，任務是找出被X包圍的O，把這些O都變成X。
規則類似圍棋，由此可以很簡單地歸納出一個結論，
不與邊界相接的O都要變成X，範例如下：

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

實作的作法其實不難，
我的作法是使用遞迴，由左上角元素往右上角元素分別進行DFS走訪，當然由右下角往左下角、左上角往左下角、右上角往右下角亦然(必須四個邊都分別進行，否則會有走訪死角，有些被圍住的O會漏掉)。
走訪過程中，如果讀到O，直接複寫成S(標記為與邊相接的O)，
如果這個O還有與其他O相接，遞迴進入下一個O，重複上面的動作。
最後，二維陣列上便會只剩下沒有與邊相接的O，
把S全部在複寫成X後輸出結果即可完成。
/* Travel 4 sides. */
/* Recursively transfer the 'O' linkd with the 'O' on the side and in the corner. */

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rowlen = board.size();
        if(rowlen==0) return;
        int collen = board.at(0).size();
     
        for(int i=0; i<collen; i++){
            check(0, i, board, rowlen, collen);
            check(rowlen-1, i, board, rowlen, collen);
        }
        for(int i=1; i<rowlen-1; i++){
            check(i, 0, board, rowlen, collen);
            check(i, collen-1, board, rowlen, collen);
        }
     
        for(int i=0; i<rowlen; i++)
            for(int j=0; j<collen;j++){
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='S')
                    board[i][j]='O';
            }
     
    }
    void check(int i, int j, vector<vector<char>>& board, int rowlen, int collen){
        if(board[i][j]=='O'){
            board[i][j]='S';
            if(i-1>0)
                if(board[i-1][j]=='O'){
                    check(i-1, j, board, rowlen, collen);
                }
            if(i+1<rowlen-1)
                if(board[i+1][j]=='O'){
                    check(i+1, j, board, rowlen, collen);
                }
            if(j-1>0)
                if(board[i][j-1]=='O'){
                    check(i, j-1, board, rowlen, collen);
                }
            if(j+1<collen-1)
                if(board[i][j+1]=='O'){
                    check(i, j+1, board, rowlen, collen);
                }
        }
    }
};

main函式中前兩個for迴圈實作四個邊的走訪，
最後一個則是將S轉成X，
check函式則是實作DFS遞迴走訪，
四個if分支判斷為邊界防呆，避免Runtime Error。