BFS解决FloodFill算法(4)_被围绕的区域

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

BFS解决FloodFill算法(4)_被围绕的区域

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
   

目录

1. 题目链接

2. 题目描述

3. 解法

算法思路:

代码展示: 

4. 算法总结


1. 题目链接

OJ链接 : 被围绕的区域icon-default.png?t=O83Ahttps://leetcode.cn/problems/surrounded-regions/description/

2. 题目描述

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' 组成,捕获 所有 被围绕的区域

  • 连接:一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域:连接所有 'O' 的单元格来形成一个区域。
  • 围绕:如果您可以用 'X' 单元格 连接这个区域,并且区域中没有任何单元格位于 board 边缘,则该区域被 'X' 单元格围绕。

通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域

示例 1:

输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解释:

在上图中,底部的区域没有被捕获,因为它在 board 的边缘并且不能被围绕。

示例 2:

输入:board = [["X"]]

输出:[["X"]]

提示:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'

3. 解法

算法思路:

正难则反, 可以先利用bfs将与边缘相连的 '0'区域做上标记, 然后重新遍历矩阵, 将没有标记过的 '0'修改成 'X'即可.

代码展示: 

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;
public:void solve(vector<vector<char>>& board) {n = board.size(), m = board[0].size();//将边缘'0'坐上标记for(int i = 0; i < m; i++){if(board[0][i] == 'O') bfs(board, 0, i);if(board[n -1][i] == 'O') bfs(board, n - 1, i);}for(int j = 0; j < n; j++){if(board[j][0] == 'O') bfs(board, j, 0);if(board[j][m - 1] == 'O') bfs(board, j, m - 1);}for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(board[i][j] == 'O') board[i][j] = 'X';else if(board[i][j] == '.') board[i][j] = 'O';}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int, int>> q;q.push({i, j});board[i][j] = '.';while(q.size()){auto [x, y] = q.front();q.pop();for(int k = 0; k < 4; k++){int a = dx[k] + x, b = dy[k] + y;if(a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O'){q.push({a, b});board[a][b] = '.';}}}}
};

 

4. 算法总结

初始化方向数组:
定义两个数组 dx 和 dy 来表示四个方向(上下左右)的偏移。

获取矩阵的尺寸:
获取矩阵的行数 n 和列数 m。

标记边缘的 'O':
遍历矩阵的四条边(上、下、左、右),对每个边上的 'O' 进行 BFS 标记:
如果边缘的某个位置是 'O',则调用 BFS 函数,将该 'O' 及其所有相连的 'O' 标记为 '.'。

遍历整个矩阵:
再次遍历整个矩阵:
将仍为 'O' 的元素转换为 'X'(表示被包围)。
将标记为 '.' 的元素恢复为 'O'(表示未被包围)。

BFS 函数:
使用队列进行 BFS,从传入的起始坐标开始:
将当前坐标的 'O' 转换为 '.'。
遍历四个方向,若相邻位置为 'O',则将其加入队列并标记为 '.'。

总结  : 

该算法通过 BFS 在边缘 'O' 的基础上进行标记, 确保与边缘相连的 'O' 不会被错误地转为 'X', 最后的遍历操作则负责将所有被包围的 'O' 转为 'X', 同时恢复未包围的 'O', 时间复杂度为 O(n * m), 其中n和m分别为矩阵的行和列数 

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

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

相关文章

【R + Python】iNaturalist 网站图片下载 inat api

文章目录 一、iNaturalist 简介二、R语言API&#xff1a;rinat三、示例3.1 获取观测数据3.2 绘制可视化图像函数用法 3.4 在区域网格中搜索3.5 下载图片3.51 提取图片 url3.52 下载图片: R语言3.53 下载图片: python 四、获取详细rinat包的文档 一、iNaturalist 简介 &#x1…

8.three.js相机详解

8.three.js相机详解 1、 认识相机 在Threejs中相机的表示是THREE.Camera&#xff0c;它是相机的抽象基类&#xff0c;其子类有两种相机&#xff0c;分别是正投影相机THREE.OrthographicCamera和透视投影相机THREE.PerspectiveCamera&#xff1a; 正投影和透视投影的区别是&am…

深度学习技术演进:从 CNN、RNN 到 Transformer 的发展与原理解析

深度学习的技术演进经历了从卷积神经网络&#xff08;CNN&#xff09;到循环神经网络&#xff08;RNN&#xff09;再到 Transformer 的重要发展。这三个架构分别擅长处理图像、序列数据和多种任务的特征&#xff0c;标志着深度学习在不同领域取得的进步。 1. 卷积神经网络&…

java智能物流管理系统源码(springboot)

项目简介 智能物流管理系统实现了以下功能&#xff1a; 智能物流管理系统的主要使用者分为管理员&#xff0c;顾客&#xff0c;员工&#xff0c;店主。功能有个人中心&#xff0c;顾客管理&#xff0c;员工管理&#xff0c;店主管理&#xff0c;门店信息管理&#xff0c;门店…

Go 语言中的 for range 循环教程

在 Go 语言中&#xff0c;for range 循环是一个方便的语法结构&#xff0c;用于遍历数组、切片、映射和字符串。本教程将通过示例代码来帮助理解如何在 Go 中使用 for range 循环。 package mainimport "fmt"func main() {// 遍历切片并计算和nums : []int{2, 3, 4}…

OpenCV视觉分析之目标跟踪(1)计算密集光流的类DISOpticalFlow的介绍

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 这个类实现了 Dense Inverse Search (DIS) 光流算法。更多关于该算法的细节可以在文献 146中找到。该实现包含了三个预设参数集&#xff0c;以提…

Visual studio 下载安装

1&#xff0c;Visual stutdio 网址 下载 Visual Studio Tools - 免费安装 Windows、Mac、Linux 2&#xff0c;下划页面&#xff0c;点击 较早的下载 3&#xff0c;选择对应的版本进行下载

蓝牙技术的多种模式详解

蓝牙作为一种广泛应用的无线通信技术&#xff0c;已经在我们的日常生活中无处不在。随着技术的发展&#xff0c;蓝牙已经不再仅限于传统的音频传输&#xff0c;而是扩展到了各种应用领域。本文将深入探讨蓝牙的各种模式及其应用场景。 1. 经典蓝牙&#xff08;BR/EDR&#xff…

单链表OJ题:移除链表元素(力扣)

目录 解法一&#xff1a;带头节点的新链表 解法二&#xff1a;不带头节点的新指向关系链表 总结 这是一道简单的力扣题目&#xff0c;关于解法的话&#xff0c;这里提供了二种思路&#xff0c;重点解释前两种&#xff0c;还有一种思路好想&#xff0c;但是时间复杂度为O(n^2…

一站式学习 Shell 脚本语法与编程技巧,踏出自动化的第一步

文章目录 1. 初识 Shell 解释器1.1 Shell 类型1.2 Shell 的父子关系 2. 编写第一个 Shell 脚本3. Shell 脚本语法3.1 脚本格式3.2 注释3.2.1 单行注释3.2.2 多行注释 3.3 Shell 变量3.3.1 系统预定义变量&#xff08;环境变量&#xff09;printenv 查看所有环境变量set 查看所有…

SMT 生产可视化:提升电子组装流程效率

通过图扑 HT 对表面贴装技术&#xff08;SMT&#xff09;生产线的实时数据采集与可视化分析&#xff0c;实现对产品质量、产能利用率和流程优化的有效监控&#xff0c;助力生产效率最大化与质量提升。

听见文本的魅力:AI 与未来的语音交互

AI 与未来的语音交互 引言什么是文本转语音&#xff08;TTS&#xff09;&#xff1f;当前 TTS 技术现状国内海外文本转语音能力调研文本转语音能力说明多情感风格SSML语音合成标记语言 未来趋势 引言 随着人工智能&#xff08;AI&#xff09;技术的迅猛发展&#xff0c;文本转…

OpenCV视觉分析之运动分析(4)背景减除类:BackgroundSubtractorKNN的一系列set函数的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 BackgroundSubtractorKNN类有一系列的set函数&#xff0c;下面我们一一列举他们的名字和用法。 一系列set函数 函数setDetectShadows() setDe…

笔记整理—linux驱动开发部分(1)驱动梗概

驱动可以分为广义上的和狭义上的驱动。广义上的驱动是用于操作硬件的代码&#xff0c;而狭义上的驱动为基于内核系统之上让硬件去被操作的逻辑方法。 linux体系架构&#xff1a; 1.分层思想 &#xff1a;在OS中间还会有许多层。 : 2.驱动的上面是系统调用&#xff08;API&…

JavaScript网页设计案例教程:从零开始构建一个响应式网页

JavaScript网页设计案例教程&#xff1a;从零开始构建一个响应式网页 前言 在当今互联网时代&#xff0c;网页设计已成为一项重要技能。JavaScript作为网页开发的核心技术之一&#xff0c;能够让网页变得更加生动和交互。本文将带您通过一个实际案例&#xff0c;逐步学习如何…

万字图文实战:从0到1构建 UniApp + Vue3 + TypeScript 移动端跨平台开源脚手架

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f343; vue-uniapp-template &#x1f33a; 仓库主页&#xff1a; Gitee &#x1f4ab; Github &#x1f…

【C语言】控制台学生成绩管理系统

文章目录 C语言编程&#xff1a;学生成绩管理系统一、程序概述二、代码实现三、程序解释 C语言编程&#xff1a;学生成绩管理系统 在这篇文章中&#xff0c;我们将一起探讨如何使用C语言来创建一个简单的学生成绩管理系统。这个系统将允许用户输入学生数量、学号和成绩&#x…

钉钉录播抓取视频

爬取钉钉视频 免责声明 此脚本仅供学习参考&#xff0c;切勿违法使用下载他人资源进行售卖&#xff0c;本人不但任何责任! 仓库地址: GItee 源码仓库 执行顺序 poxyM3u8开启代理getM3u8url用于获取m3u8文件userAgent随机请求头downVideo|downVideoThreadTqdm单线程下载和…

水轮发电机油压自动化控制系统解决方案介绍

在现代水电工程中&#xff0c;水轮机组油压自动化控制系统&#xff0c;不仅直接关系到水轮发电机组的安全稳定运行&#xff0c;还影响着整个水电站的生产效率和经济效益。 一、系统概述 国科JSF油压自动控制系统&#xff0c;适用于水轮发电机组调速器油压及主阀&#xff08;蝶…

Golang | Leetcode Golang题解之第503题下一个更大元素II

题目&#xff1a; 题解&#xff1a; func nextGreaterElements(nums []int) []int {n : len(nums)ans : make([]int, n)for i : range ans {ans[i] -1}stack : []int{}for i : 0; i < n*2-1; i {for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i%…