Surrounded Regions

LeetCode #130

Description:

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.

Example:

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

Idea:

对boundary的node来DFS或者BFS，访问的时候把"O" mark as "M"。最后，把所有"O"变成"X",把"M"变回去"O"。

DFS和BFS都可以，但是DFS recursion会超时，自己写stack可以。

Code:

BFS，先访问再入queue，pass test

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;

        int m=board.size();
        int n=board[0].size();

        for(int i=0; i<m; ++i){
            if(board[i][0]=='O'){
                BFS(board, i, 0);
            }
            if(board[i][n-1]=='O'){
                BFS(board, i, n-1);
            }

        }

        for(int j=0; j<n; ++j){
            if(board[0][j]=='O'){
                BFS(board, 0, j);
            }
            if(board[m-1][j]=='O'){
                BFS(board, m-1, j);
            }

        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                else if(board[i][j]=='M'){
                    board[i][j]='O';
                }
            }
        }

    }

    void BFS(vector<vector<char>>& board, int i, int j){
        queue<pair<int,int>> b_queue;
        board[i][j]='M';  // Visit

        b_queue.push(make_pair(i, j));

        int m=board.size();
        int n=board[0].size();

        vector<pair<int, int>> move={{-1,0}, {0,1}, {1,0}, {0,-1}};

        while(!b_queue.empty()){
            pair<int, int> element = b_queue.front();
            b_queue.pop();

            int k=element.first;
            int l=element.second;

            for(auto e: move){
                int k_next=k+e.first;
                int l_next=l+e.second;
                if(k_next>=0 && k_next<m && l_next>=0 && l_next<n && board[k_next][l_next]=='O'){
                    board[k_next][l_next]='M'; // Visit node, then push into queue
                    b_queue.push(make_pair(k_next, l_next));
                }

            }
        }

    }
};

BFS, 也可以pass test。先入queue，如果没visited，visit，然后把children里符合条件的push入queue。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;

        int m=board.size();
        int n=board[0].size();

        for(int i=0; i<m; ++i){
            if(board[i][0]=='O'){
                BFS(board, i, 0);
            }
            if(board[i][n-1]=='O'){
                BFS(board, i, n-1);
            }

        }

        for(int j=0; j<n; ++j){
            if(board[0][j]=='O'){
                BFS(board, 0, j);
            }
            if(board[m-1][j]=='O'){
                BFS(board, m-1, j);
            }

        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                else if(board[i][j]=='M'){
                    board[i][j]='O';
                }
            }
        }

    }

    void BFS(vector<vector<char>>& board, int i, int j){
        queue<pair<int,int>> b_queue;

        b_queue.push(make_pair(i, j));

        int m=board.size();
        int n=board[0].size();

        vector<pair<int, int>> move={{-1,0}, {0,1}, {1,0}, {0,-1}};

        while(!b_queue.empty()){
            pair<int, int> element = b_queue.front();
            b_queue.pop();

            int k=element.first;
            int l=element.second;

            if(board[k][l]!='M'){ // If not visited, visit
                board[k][l]='M'; 

                for(auto e: move){
                    int k_next=k+e.first;
                    int l_next=l+e.second;
                    if(k_next>=0 && k_next<m && l_next>=0 && l_next<n && board[k_next][l_next]=='O'){
                        b_queue.push(make_pair(k_next, l_next));
                    }

                }                
            }
        }

    }
};

DFS， 用stack自己写会pass，用recursive会超时。 先入stack，如果没visited，visit，然后把children里符合条件的push入stack。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;

        int m=board.size();
        int n=board[0].size();

        for(int i=0; i<m; ++i){
            if(board[i][0]=='O'){
                DFS(board, i, 0);
            }
            if(board[i][n-1]=='O'){
                DFS(board, i, n-1);
            }

        }

        for(int j=0; j<n; ++j){
            if(board[0][j]=='O'){
                DFS(board, 0, j);
            }
            if(board[m-1][j]=='O'){
                DFS(board, m-1, j);
            }

        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                else if(board[i][j]=='M'){
                    board[i][j]='O';
                }
            }
        }

    }

    void DFS(vector<vector<char>>& board, int i, int j){
        stack<pair<int,int>> b_stack;

        b_stack.push(make_pair(i, j));

        int m=board.size();
        int n=board[0].size();

        vector<pair<int, int>> move={{-1,0}, {0,1}, {1,0}, {0,-1}};

        while(!b_stack.empty()){
            pair<int, int> element = b_stack.top();
            b_stack.pop();

            int k=element.first;
            int l=element.second;

            if(board[k][l]!='M'){ // if not visited, visit
                board[k][l]='M';  

                for(auto e: move){
                    int k_next=k+e.first;
                    int l_next=l+e.second;
                    if(k_next>=0 && k_next<m && l_next>=0 && l_next<n && board[k_next][l_next]=='O'){
                        b_stack.push(make_pair(k_next, l_next));
                    }
                }                
            }
        }

    }
};

DFS，会超时

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;

        int m=board.size();
        int n=board[0].size();

        for(int i=0; i<m; ++i){
            if(board[i][0]=='O'){
                DFS(board, i, 0);
            }
            if(board[i][n-1]=='O'){
                DFS(board, i, n-1);
            }

        }

        for(int j=0; j<n; ++j){
            if(board[0][j]=='O'){
                DFS(board, 0, j);
            }
            if(board[m-1][j]=='O'){
                DFS(board, m-1, j);
            }

        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                else if(board[i][j]=='M'){
                    board[i][j]='O';
                }
            }
        }

    }

    void DFS(vector<vector<char>>& board, int i, int j){
        board[i][j]='M';

        int m=board.size();
        int n=board[0].size();

        vector<pair<int, int>> move={{-1,0}, {0,1}, {1,0}, {0,-1}};

        for(auto e: move){
            int k=i+e.first;
            int l=j+e.second;

            if(k>=0 && k<m && l>=0 && l<n && board[k][l]=='O'){
                DFS(board, k, l);
            }
        }

    }
};