Leetcode 130 Surrounded Regions

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.

For example,

代码语言：javascript复制

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

代码语言：javascript复制

X X X X
X X X X
X X X X
X O X X

把不和边界联通的O全部变成X

从边界上的O开始搜索相邻的O，并打上标记，最后把没有打上标记的全部置为X

代码RE了，Leetcode 6万多层就RE了,还能说什么呢？，强行逼人用BFS，好烦啊！

贴个错的心血，写不动了。

代码语言：javascript复制

class Solution {
public:
    void dfs(vector<int>& vis, vector<vector<char>>& board, int now)
    {
        vis[now]=1;
        int x=now/board[0].size();
        int y=now%board[0].size();
        int addx[4]={1,-1,0,0};
        int addy[4]={0,0,1,-1};
        for(int i=0;i<4;i  )
        {
            int xx=x addx[i];
            int yy=y addy[i];
            if(xx>=0 && xx<board.size() && yy>=0 && yy<board[0].size() && board[xx][yy]=='O' && !vis[xx*board[0].size() yy]) 
            dfs(vis,board,xx*board[0].size() yy); 
        }
    }
    void solve(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty()) return ;
        vector<int> edge;
        vector<int> vis(board.size()*board[0].size(),0);
        for(int i=0;i<board.size();i  )
        {
            if(board[i][0] == 'O') edge.push_back(i*board[0].size());
            if(board[i][board[0].size()-1] == 'O') edge.push_back((i 1)*board[0].size()-1);
        }
        for(int i=0;i<board[0].size();i  )
        {
            if(board[0][i] == 'O') edge.push_back(i);
            if(board[board.size()-1][i]=='O') edge.push_back((board.size()-1)*board[0].size() i);
        }
        for(int i=0;i<edge.size();i  )
        {
            if(vis[edge[i]]) continue;
            dfs(vis,board,edge[i]);
        }
        for(int i=0;i<board.size();i  )
            for(int j=0;j<board[0].size();j  )
                if(board[i][j]=='O' && !vis[i*board[0].size() j])board[i][j]='X';
    }
};

capture function leetcode

0 人点赞