leetcode130. Surrounded Regions

focusj 发布于2019-08-16 10:45 / 1643人阅读

摘要：将所有和边界相连的都标记出来。那么当我重新遍历数组的时候，剩下的则是被完全包围的。

题目要求

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

将所有被X环绕的O区域获取出来并转化为X

思路与代码

这篇题目与leetcode200. Number of Islands思路非常相近，建议毫无思路的同学先参考一下这篇博客。其实这种将区域相连的题目往往都可以使用深度优先遍历或者是Union-Find方法来实现。在这里我就给出深度优先遍历的实现方法，有兴趣的同学可以参考上文的博客来自己实现Union-Find方法。

和leetcode200题不同，在本题中，只有被完全包围的图形才可以被选中与转化，也就是，任何一个和数组边界上的O相连的都不可能是完全包围。所以在这题里我们采用逆向思维。将所有和边界O相连的O都标记出来。那么当我重新遍历数组的时候，剩下的O则是被完全包围的。

代码如下：

    public void solve(char[][] board) {
        if(board.length<=2 || board[0].length<=2 ) return;
        int row = board.length;
        int column = board[0].length;
        for(int i = 0 ; i=board.length || j>=board[0].length) return;
        if(board[i][j] == "X" || board[i][j]=="*") return;
        board[i][j] = "*";
        if(i>1 && board[i-1][j]=="O") boundarySearch(board, i-1, j);
        if(j>1 && board[i][j-1]=="O") boundarySearch(board, i, j-1);
        if(i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管海外云主机 Regions Surrounded 130美元 cdn130

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70403.html

[Leetcode] Surrounded Regions 找出被包围的区域

摘要：原题链接边缘搜索替换法复杂度时间空间思路从矩阵的四条边上的点作为起点，搜索连续的一块区域上值为的点并赋为一个临时变量。对四条边上所有点都进行过这个步骤后，矩阵内剩余的就是被包围的。 Surrounded Regions Given a 2D board containing X and O, capture all regionssurrounded by X. A region i...

miguel.jiang 2019-08-14 16:10 评论0 收藏0
[LintCode] Surrounded Regions

摘要：先用处理左右边界上的换成再用处理上下边界除去四角的换成把剩下的没有被处理过，也就是被包围的置为把所有暂时置为的不被包围的换回如当前字符的坐标越界不是，返回是的都置为，然后迭代其上下左右各点 Problem Given a 2D board containing X and O, capture all regions surrounded by X.A region is captur...

Labradors 2019-08-14 15:11 评论0 收藏0
Leetcode之Union-Find(并查集)

摘要：并查集包括查询和联合，主要使用不相交集合查询主要是用来决定不同的成员是否在一个子集合之内联合主要是用来把多个子集合成一个集合的实际运用计算机网络检查集群是否联通电路板检查不同的电路元件是否联通初始化联通与检测与是否联通返回联通的数并查集(Union-Find)包括查询(Find)和联合(Union)，主要使用不相交集合(Disjoint-Sets)查询(Find)主要是用来决定不同的...

roland_reed 2019-08-15 13:44 评论0 收藏0
【LC总结】Union Find系列(Num of Islands I&II/Graph V

摘要：不得不说，对于这道题而言，是一种很木讷的模板。主函数按矩阵大小建立一个类进行后续操作一个结点用来连接边角不可能被围绕的一个函数对矩阵元素进行结点线性化。同理，，，在主函数中初始化后调用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...

bergwhite 2019-08-14 15:51 评论0 收藏0
leetcode200. Number of Islands

摘要：题目要求提供一个二维数组表示一张地图，其中代表陆地，代表海洋。这里使用一个新的二维数组来表示对应地图上的元素属于哪个并查集。在合并的时候先进行判断，如果二者为已经相连的陆地，则无需合并，否则将新的二维数组上的元素指向所在的并查集。题目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...

Zoom 2019-08-16 10:45 评论0 收藏0