首页 > 代码库 > Leetcode Surrounded Regions

Leetcode Surrounded Regions

2024-07-08 21:32:27   226人阅读

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.

For example,

X X X XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

题目不难理解，就是把被X包围的O变成X，从题目给出的例子可以看出，只有在边界有O的地方，才不会被X包围，
故将起始搜索位置缩小为边界，常用的搜索方法为深搜和广搜
最开始题目采用深搜去解决发现题目ac不了，深搜的最大深度可能为n*m，但空间复杂度为O(1)
下面提供深搜代码
int dx[] = {-1,0,1,0};int dy[] = {0,1,0,-1};class Solution {public:typedef vector<vector<char> > Board;void dfs(int x, int y, Board& board){    if(x < 0 || x >= board.size() || y < 0 || y >=board[0].size() || board[x][y]!=‘O‘) return;    board[x][y] = ‘Y‘;    for(int i = 0 ; i < 4; ++ i){        dfs(x+dx[i],y+dy[i],board);    }}void solve(vector<vector<char> > &board){    if(board.size() == 0) return;    int n = board.size(),m = board[0].size();    for(int i = 0 ; i < n; ++ i){        dfs(i,0,board);        dfs(i,m-1,board);    }    for(int j = 0; j < m; ++ j){        dfs(0,j,board);        dfs(n-1,j,board);            }    for(int  i = 0 ; i < n ; ++ i){        for(int j = 0 ; j < m ; ++ j){            board[i][j]=(board[i][j]==‘Y‘?‘O‘:‘X‘);        }    }}
View Code

故本题用广搜去解决，广搜的最大深度为max(n,m)，但要开辟一个queue，故其空间复杂度为O(max(n,m))

 
int dx[] = {-1,0,1,0};int dy[] = {0,1,0,-1};typedef pair<int,int> Point;typedef vector<vector<char> > Board;queue<Point> que;void bfs(Board& board){    while(!que.empty()){        Point p = que.front();que.pop();        board[p.first][p.second]=‘Y‘;        for(int i = 0 ; i < 4; ++ i){            int newX = x+dx, newY = y+dy;            if(newX>=0 && newX<board.size() && newY>=0 && newY< board.size() && board[newX][newY]==‘O‘ )                 que.push(Point(newX,newY));        }    }}void solve(vector<vector<char> >& board){    if(board.size() == 0) return;    int n = board.size(),m = board[0].size();    for(int i = 0 ; i < n; ++ i){        if(board[i][0] == ‘O‘) que.push(Point(i,0));        if(board[i][m-1] == ‘O‘) que.push(Point(i,m-1));    }    bfs(board);    for(int j = 0; j < m; ++ j){        if(board[0][j] == ‘O‘) que.push(Point(0,j));        if(board[n-1][j] == ‘O‘) que.push(Point(n-1,j));    }    bfs(board);    for(int  i = 0 ; i < n ; ++ i){        for(int j = 0 ; j < m ; ++ j){            board[i][j]=(board[i][j]==‘Y‘?‘O‘:‘X‘);        }    }}
 






























        

            
                
                  
                
                

                    联系

                    我们