【Leetcode】130. Surrounded Regions（DFS）

我不是女神ヾ 2022-02-12 11:17 165阅读 0赞

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:**

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

题目大意：

二维表中，将被X包围的O全部转换成X。

解题思路：

那么其中满足条件的只可能是边界上或者与边界相连的O能够幸免于难。

所以每次找到边界上等于O时，DFS将其和与其相连的都标记为\#。

class Solution {
    private:
        int x[4]={-1,1,0,0};
        int y[4]={0,0,1,-1};
        vector<vector<int>> begin_point;
        bool valid(vector<vector<char> >& board, int cor_x, int cor_y){
            if(cor_x>=0&&cor_x<board.size()&&cor_y>=0&&cor_y<board[0].size()&&board[cor_x][cor_y]=='O'){
                return true;
            }
            return false;
        }
        void dfs(vector<vector<char> >& board, int cor_x, int cor_y){
            
            if(board[cor_x][cor_y]=='O'){
                board[cor_x][cor_y] = '#';
            }
            
            for(int i=0;i<4;i++){
                int xx = cor_x + x[i];
                int yy = cor_y + y[i];
                if(valid(board, xx, yy)){
                    dfs(board, xx, yy);
                }
            }
            
        }
        
    public:
        void solve(vector<vector<char>>& board) {
            if(board.size()==0) return;
            for(int i=0;i<board.size();i++){
                for(int j=0;j<board[0].size();j++){
                    
                    if(i==0||i==board.size()-1||j==0||j==board[0].size()-1){
                        if(board[i][j]=='O'){
                            // vector<int> tmp;
                            // tmp.push_back(i);
                            // tmp.push_back(j);
                            dfs(board, i, j);
                        }
                        // begin_point.push_back(tmp);
                    }
                }
            }  
            
            for(int i=0;i<board.size();i++){
                for(int j=0;j<board[0].size();j++){
                    if(board[i][j]=='O'){
                        board[i][j]='X';
                    }
                    else if(board[i][j]=='#'){
                        board[i][j]='O';
                    }
                }
            } 
            
        }
    };