Leetcode 130 Surrounded Regions

triplebee

发布于 2018-01-12 14:52:01

4910

发布于 2018-01-12 14:52:01

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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,

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

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

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

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

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

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';
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-10-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

capture