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

news/2024/6/20 21:06:16/文章来源:https://blog.csdn.net/lyx200154/article/details/137228380

. - 力扣(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.luyixian.cn/news_show_1033286.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

1.5编写一个程序,输入梯形的上底,下底和高,输出梯形的面积。

1、编写一个程序,输入梯形的上底,下底和高,输出梯形的面积。 package com.kangning.web.controller.system;import java.util.Scanner;/*** 编写一个程序,输入梯形的上底,下底和高,输出梯形的面积。*/ public class CountArea {public static void main(String[] args) …

【操作系统】想要更好的学习计算机,操作系统的知识必不可少!!!

操作系统的概念 导言一、日常生活中的操作系统二、计算机系统层次结构三、操作系统的定义3.1 控制和管理计算机资源3.2 组织、调度计算机的工作与资源的分配3.3 给用户和其他软件提供方便接口与环境3.4 总结 四、操作系统的目标和功能4.1 作为管理者4.1.1 处理机管理4.1.2 存储…

【A-006】基于SSH的新闻发布系统(含论文)

【A-006】基于SSH的新闻发布系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Jdk7(8)Tomcat7(8)MySQLIntelliJ IDEA(Eclipse) 数据库&#xff1a; MySQL 技术&#xff1a; SpringStruts2HiberanteJSPJquery 适用于&#xff1a; 课程设计&#xff0c;毕业设计&…

算法系列--递归,回溯,剪枝的综合应用(1)

&#x1f495;"对相爱的人来说&#xff0c;对方的心意&#xff0c;才是最好的房子。"&#x1f495; 作者&#xff1a;Lvzi 文章主要内容&#xff1a;算法系列–递归,回溯,剪枝的综合应用(1) 大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(1) 1.全排…

Higress 基于自定义插件访问 Redis

作者&#xff1a;钰诚 简介 基于 wasm 机制&#xff0c;Higress 提供了优秀的可扩展性&#xff0c;用户可以基于 Go/C/Rust 编写 wasm 插件&#xff0c;自定义请求处理逻辑&#xff0c;满足用户的个性化需求&#xff0c;目前插件已经支持 redis 调用&#xff0c;使得用户能够…

蓝桥杯-岛屿个数

solution 数1的块数题&#xff0c;加了内岛不计入的小限制&#xff0c;以及输入数据间没有空格&#xff0c;不是矩阵形式的整数输入。 判断是否是子岛屿&#xff1a;如果该岛屿有边缘部分或者可以通过外海走到边缘部分说明不是子岛屿 #include<iostream> #include<…

Django创建多app应用

目录 1. 引言 2. 多app创建的两种方式 2.1 多个app结构 2.2 单个apps多个app 3. 最后 1. 引言 在平常业务开发中&#xff0c;我们遇到的功能可能会有很多&#xff0c;单个app的应用可能无法满足我们 这个时候&#xff0c;我们就需要多app应用&#xff0c;例如&#xff1a…

基于SSM+Jsp+Mysql的固定资产管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

在线考试系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读300套最新项目持续更新中..... 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 2024年56套包含ja…

Linux 系统 安装redis

Linux 系统 安装redis 下载redis安装包&#xff0c;并上传到服务器指定安装目录 一、解压安装包并安装 1、 tar xzf redis-4.0.9.tar.gz 2、先通过gcc -v是否有安装gcc&#xff0c;如果没有安装 统一安装Gcc rpm -Uvh *.rpm --nodeps --force 3、cd /usr/local/red…

前端之HTML——网页的骨架!!

目录 一、HTML介绍 二、HTML标签 &#xff08;一&#xff09;基础标签 &#xff08;二&#xff09;其他标签 2.1 6个常用标签 2.2 8个文本标签 2.3 6个列表标签 2.4 4个表格标签 2.5 4个媒体标签 2.6 1个嵌入标签 2.7 …

HBuilder uniapp发行h5遇到报错:此应用 DCloud appid 为 __UNI__95950AD ,您不是这个应用的项目成员。

uniapp打包遇到不是项目成员问题&#xff0c;如下截图&#xff1a; 解决方法如下&#xff1a; 打开项目的mainfest.json文件&#xff0c;在AppID位置点击重新获取&#xff0c;获取后重新点发行打包即可 另遇到HBuilder账号认证问题&#xff0c;如公司wifi打不开认证地址&#…

一文入门Ubuntu22

目录 1.安装Ubuntu22 2.常用目录 3.常用指令 1.sudo 超级用户权限运行命令 2.ls 罗列当前文件信息 3.文件目录相关&#xff1a; 1.cd改变工作路径&#xff1a; 2.pwd 3.创建目录和文件&#xff1a; 4.which 5.ps 6.kill 7.ping 4.用户相关 5.ssh与scp 6.服务相关…

【氮化镓】GaN器件中关态应力诱导的损伤定位

概括总结&#xff1a; 这项研究通过低频1/f噪声测量方法&#xff0c;探究了在关态&#xff08;OFF-state&#xff09;应力作用下&#xff0c;AlGaN/GaN高电子迁移率晶体管&#xff08;HEMTs&#xff09;中由应力引起的损伤的定位。研究中结合了电致发光&#xff08;EL&#xf…

谈谈MVCC机制

在MySQL中&#xff0c;MVCC&#xff08;多版本并发控制&#xff09;是InnoDB存储引擎使用的并发控制机制。它提供对数据的并发访问&#xff0c;并确保多用户环境中数据的一致性和隔离性。 InnoDB通过“Undo log”存储每条记录的多个版本&#xff0c;提供历史记录供读取&#x…

Spring Boot项目启动速度优化

1、配置自动配置排除列表&#xff0c;减少启动自动配置扫描&#xff0c;配置项spring.autoconfigure.exclude 2、启动类添加索引注解Indexed&#xff0c;去除启动过程中 Components 的扫描步骤&#xff0c;直接从索引文件读取。 import org.springframework.stereotype.lndexe…

自定义 Unity Scene 的界面工具

介绍 文档中会进行SceneView的自定义扩展&#xff0c;实现显示常驻GUI和添加自定义叠加层&#xff08;Custom Overlay&#xff09;。 最近项目开发用回了原生的Unity UI相关内容。对于之前常用的FairyGUI来说&#xff0c;原生的UGUI对于UI同学来讲有些不太方便。再加上这次会…

【精品方案】智慧金融大数据分析平台总体架构方案

以下是部分PPT内容&#xff0c;请您参阅。如需下载完整PPTX文件&#xff0c;请前往星球获取&#xff1a; 1.实现数据共享 通过数据平台实现数据集中&#xff0c;确保金融集团各级部门均可在保证数据隐私和安全的前提下使用数据&#xff0c;充分发挥数据作为企业重要资产的业务价…

String Encryptor custom Bean not found with name ‘jasyptStringEncryptor‘...

项目采用 spring boot 2.6.13 jasypt-spring-boot-starter 3.0.5 apollo-client 1.6.0 自定义jasyptStringEncryptor&#xff0c;服务器上启动死活报找不到bean jasyptStringEncryptor&#xff0c;采用默认的&#xff0c;密文配置项自然解密失败导致服务无法启动。 经过一…

华为云RDS for Mysql入门与配置

华为云RDS for MySQL支持混合SSD实例&#xff0c;它结合了华为云容器、本地SSD盘和高速云盘。 优势&#xff1a; 主备实例提供故障自动切换和手动切换&#xff0c;业务中断时间为秒级&#xff0c;以及异地灾难备份&#xff0c;最大程度上在出现故障的情况下保障整个数据库集群…