算法——矩阵,被围绕的区域

2024-04-02 16:12
文章标签 算法 区域 矩阵 围绕

本文主要是介绍算法——矩阵,被围绕的区域,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

. - 力扣(LeetCode)

最开始也是考虑使用dfs,对于矩阵中的每个点,如果能到达边界的O,则跳过继续dfs。否则如果上下左右四个方向都无法到达边界的O,则说明当前的无法到达,在一个set中记录他的行数列数。

最后对每个记录的点标记为X即可。

但是有问题,首先可能会出现永久递归无法跳出来。如果使用父节点记录当前节点的前一个节点,则如果父节点恰好通往边界O,会导致错误。使用visited来记录状态也不行。

应该反向思维,从每个边界O出发dfs。

思路:对于边界上的每一个点进行dfs。如果当前点为X则直接跳过。如果当前点为O,则把O该为A,继续dfs。

使用A来记录从边界上的O所能够到达的点。

遍历完之后,再把矩阵中的O改为X,表示未与边界O相连。把矩阵中的A该为O,表示与边界相连的O,不变。

注意dfs函数中,如果发现不是X不能直接else,而要判断是不是为O,为O才继续dfs。

如果不这样的话当前为A也会继续dfs,导致永远无法停止的递归。

class Solution {
public:void dfs(vector<vector<char>>& board,int row,int col){if(board[row][col]=='X')return;else if(board[row][col]=='O'){board[row][col]='A';if(row>0)dfs(board,row-1,col);if(row<board.size()-1)dfs(board,row+1,col);if(col>0)dfs(board,row,col-1);if(col<board[0].size()-1)dfs(board,row,col+1);}}void solve(vector<vector<char>>& board) {for(int i=0;i<board.size();i++){dfs(board,i,0);dfs(board,i,board[0].size()-1);}for(int i=1;i<board[0].size()-1;i++){dfs(board,0,i);dfs(board,board.size()-1,i);}for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]=='O')board[i][j]='X';else if(board[i][j]=='A')board[i][j]='O';}}}
};

这篇关于算法——矩阵,被围绕的区域的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/870443

相关文章

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

Java内存区域与内存溢出异常的详细探讨

《Java内存区域与内存溢出异常的详细探讨》:本文主要介绍Java内存区域与内存溢出异常的相关资料,分析异常原因并提供解决策略,如参数调整、代码优化等,帮助开发者排查内存问题,需要的朋友可以参考下... 目录一、引言二、Java 运行时数据区域(一)程序计数器(二)Java 虚拟机栈(三)本地方法栈(四)J

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为