搜索（DFS）---填充封闭区域

野性酷女 2021-11-29 07:56 254阅读 0赞

### 填充封闭区域 ###

[130. Surrounded Regions (Medium)][130. Surrounded Regions _Medium]

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'。

思路分析：

我们先将与边界上所有O相联通的O标记，然后遍历数组，遇见未被标记的O就将其换成X，这样就能保证所有被X包围的O都被替换成X。

代码：

class Solution { public void solve(char [][]board){ if(board==null||board.length==0) return ; int m=board.length; int n=board[0].length; for(int i=0;i<n;i++){ if(board[0][i]=='O'){ //上边界 dfs(board,0,i); } if(board[m-1][i]=='O'){ //下边界 dfs(board,m-1,i); } } for(int j=0;j<m;j++){ if(board[j][0]=='O') dfs(board,j,0); if(board[j][n-1]=='O') dfs(board,j,n-1); } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; if(board[i][j]=='0')//与边界联通的O board[i][j]='O'; } } return; } public void dfs(char[][]board,int i,int j){ //标记与边界O相连的O if(board[i][j]!='O') return ; board[i][j]='0'; if(i+1<board.length) dfs(board,i+1,j); if(i-1>=0) dfs(board,i-1,j); if(j+1<board[0].length) dfs(board,i,j+1); if(j-1>=0) dfs(board,i,j-1); } }

转载于:https://www.cnblogs.com/yjxyy/p/11110400.html

[130. Surrounded Regions _Medium]: https://leetcode.com/problems/surrounded-regions/description/

发表评论取消回复

表情：

评论列表（有 0 条评论，254人围观）

还没有评论，来说两句吧...

相关阅读

相关深度优先搜索（DFS）

文章目录一、简介二、DFS的代码实现三、代码测试一、简介深度优先搜索是一种常见的图搜索算法，它可以用于寻找图中从起点到终点的路径或遍历

小灰灰/ 2024年03月22日 14:50/ 0 赞/ 121 阅读

相关被围绕的区域(dfs)

> 原创公众号：bigsai 欢迎加入力扣打卡 > 文章已收录在 [全网都在关注的数据结构与算法学习仓库][Link 1] 欢迎star 题目描述给定一个二维的矩

小咪咪/ 2022年11月03日 11:57/ 0 赞/ 163 阅读

相关 DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节

缺乏、安全感/ 2022年10月30日 04:26/ 0 赞/ 216 阅读

相关区域填充

一、种子填充算法区域是指光栅网络上的一组像素，区域填充是把某确定的像素值送入到区域内部的所有像素中。区域填充方法分为两大类：区域由多边形围成，区域由多边形的顶

短命女/ 2022年10月01日 00:52/ 0 赞/ 249 阅读

相关区域填充算法

区域填充算法一．目的：掌握有序编表法的基本原理与实现，了解简单的交互技术。二．要求： 1. 边界种子交互输入； 2. 实例包含有凹凸多边形类型；

川长思鸟来/ 2022年08月18日 12:28/ 0 赞/ 2 阅读

相关【搜索】泡泡龙 DFS

题目描述这是一个简化版的网络游戏：在一个N×N方块构成的棋盘中，每个方块均涂上红、黄、蓝、绿（记为l、2、3、4）中的一种颜色，游戏者可以在最底行任意找一个方

淡淡的烟草味﹌/ 2022年06月10日 23:41/ 0 赞/ 205 阅读

相关多边形区域填充算法－－扫描线种子填充算法

[http://blog.csdn.net/orbit/article/details/7343236][http_blog.csdn.net_orbit_article_de

我就是我/ 2022年06月01日 05:13/ 0 赞/ 247 阅读

相关搜索理解（DFS BFS）

DFS：深搜是从当前位置一次所能到达的位置，一个位置一个位置的去查找，当遇到不能在行走时（即不符合条件时），return;返回到上一层函数，当试探完一个

系统管理员/ 2022年05月19日 02:08/ 0 赞/ 199 阅读

相关深度优先搜索（DFS）

DFS是相对于BFS的另一个中图搜索算法，其与BFS最大的不同在于它是深度优先，它会优先顺着一条路径走到底，一旦某个节点邻接的节点都被发现了，就会回溯到前面一个节点，直

以你之姓@/ 2022年05月15日 01:13/ 0 赞/ 277 阅读

相关搜索（DFS）---填充封闭区域

填充封闭区域 [130. Surrounded Regions (Medium)][130. Surrounded Regions _Medium] For e

野性酷女/ 2021年11月29日 07:56/ 0 赞/ 255 阅读