[LeetCode] Surrounded Regions

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 .

The trick is to search from the edge, but not inside the whole region.

These 4 images show how the trick works.

12 3 4

Search all elements on the edge of this region, if find ‘O’, mark it as something else, for instance ‘H’, and search the adjacent elements of this element (up, down, left, right), if find, mark it as ‘H’, and go on searching. Actually we can use a stack helping us, first we push every elements on the edge in stack, and as we searching, push new found ‘O’ element in stack, when the stack is empty, means the search is finish.

By this method, we will never reach ‘O’ that is surrounded by ‘X’, so every ‘H’ is non-surrounded ones, so we re-assignment all non-H elements as X, and ‘H’ elements as O, done.

    stack<int> sx;
    stack<int> sy;
    void solve(vector<vector<char> > &board) {
        if(board.empty()) return;
        if(board[0].empty()) return;
        int row = board.size();
        int col = board[0].size();
        for(int i=0; i<row; i++){
            if(board[i][0] == 'O'){
                sx.push(0);
                sy.push(i);
            }
            if(board[i][col - 1] == 'O'){
                sx.push(col - 1);
                sy.push(i);
            }
        }
        for(int i=0; i<col; i++){
            if(board[0][i] == 'O'){
                sx.push(i);
                sy.push(0);
            }
            if(board[row - 1][i] == 'O'){
                sx.push(i);
                sy.push(row - 1);
            }
        }
        int ymax = row - 1;
        int xmax = col - 1;
        while(!sx.empty()){
            int x = sx.top();
            int y = sy.top();
            sx.pop();
            sy.pop();
            board[y][x] = 'a';
            if(y > 0 && board[y - 1][x] == 'O'){
                sx.push(x);
                sy.push(y - 1);
            }
            if(y < ymax && board[y + 1][x] == 'O'){
                sx.push(x);
                sy.push(y + 1);
            }
            if(x > 0 && board[y][x - 1] == 'O'){
                sx.push(x - 1);
                sy.push(y);
            }
            if(x < xmax && board[y][x + 1] == 'O'){
                sx.push(x + 1);
                sy.push(y);
            }
        }
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                board[i][j] = (board[i][j] == 'a' ? 'O' : 'X');
            }
        }
    }

🙂

 

 

 

This entry was posted in Algorithm, LeetCode and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*