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,

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

业界 | 谷歌开源DeepLearn.js:可实现硬件加速的机器学习JavaScript库

选自GitHub 机器之心编译 参与:蒋思源、路雪 deeplearn.js 是一个可用于机器智能并加速 WebGL 的开源 JavaScript 库。de...

39480
来自专栏人工智能LeadAI

TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

19540
来自专栏伦少的博客

spark ML算法之线性回归使用

转载请务必注明原创地址为:http://dongkelun.com/2018/04/09/sparkMlLinearRegressionUsing/

71830
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

12920
来自专栏owent

POJ PKU 1986 Distance Queries 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

8620
来自专栏漫漫深度学习路

tensorflow自定义op:梯度

tensorflow自定义op,梯度 tensorflow 是 自动微分的,但是如果你不给它定义微分方程的话,它啥也干不了 在使用 tensorflow 的时...

85570
来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

10730
来自专栏用户2442861的专栏

从B 树、B+ 树、B* 树谈到R 树

说明:本文从B树开始谈起,然后论述B+树、B*树,最后谈到R 树。其中B树、B+树及B*树部分由weedge完成,R 树部分由Frankie完成,全文最终由Ju...

37510
来自专栏漫漫深度学习路

tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

57660
来自专栏Bingo的深度学习杂货店

Q63 Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

9840

扫码关注云+社区

领取腾讯云代金券