leetcode 130. 被围绕的区域

爱被打了一巴掌 2023-10-09 09:37 32阅读 0赞

**从边缘的O开始深搜，走过的地方置为\#**  
**从头开始，把O的地方变成X**  
**把\#的地方变成O**

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    
    class Solution { 
    public:
        void dfs(vector<vector<char>>& board,int i,int j){ 
            if( i>=0 && i<board.size() && j >= 0 && j<board[0].size() && board[i][j] == 'O' ){ 
                board[i][j] = '#';
                dfs( board,i+1,j );
                dfs( board,i-1,j );
                dfs( board,i,j+1 );
                dfs( board,i,j-1 );
            }
    
        }
        void solve(vector<vector<char>>& board) { 
            if(board.size()==0){ 
                return;
            }
            //debug(1)
            for(int i = 0;i < board[0].size();i ++){ 
                //debug(1)
                if( board[0][i] == 'O'){ 
                    //debug(2)
                    dfs(board,0,i);
                }
                if( board[board.size()-1][i] == 'O' ){ 
                    //debug(3)
                    dfs(board,board.size()-1,i);
                }
            }
            //debug(1)
            for(int i = 0;i < board.size();i ++){ 
                if(  board[i][0] == 'O'){ 
                    dfs(board,i,0  );
                }
                if( board[ i ][ board[0].size()-1 ] ){ 
                    dfs( board,i,board[0].size()-1 );
                }
            }
            for(int i=0;i<board.size();i++){ 
                for(int j=0;j<board[i].size();j++){ 
                    if(board[i][j] == 'O' ){ 
                        board[i][j] = 'X';
                    }else if(board[i][j] == '#' ){ 
                        board[i][j] = 'O';
                    }
                }
            }
    
        }
    };
    
    int main()
    { 
        Solution Solution1;
    
        vector<vector<char>> board = { 
            { 'X','X','X','X'},
            { 'X','O','O','X'},
            { 'X','X','O','X'},
            { 'X','O','X','X'},
        };
    
        Solution1.solve(board);
        for(auto i:board){ 
            for(auto j:i){ 
                cout<<j<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190924214828274.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3,size_16,color_FFFFFF,t_70