岛屿数量 广搜版BFS C#

和之前的卡码网深搜版是一道题  力扣第200题 

99. 岛屿数量

题目描述

给定一个由 1(陆地)和 0(水)组成的矩阵,你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成,并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M,表示矩阵的行数和列数。

后续 N 行,每行包含 M 个数字,数字为 1 或者 0。

输出描述

输出一个整数,表示岛屿的数量。如果不存在岛屿,则输出 0。

输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
3
提示信息

根据测试案例中所展示,岛屿数量共有 3 个,所以输出 3。

数据范围:

1 <= N, M <= 50

 思路:广度优先搜索:如果一个位置为 1,则将其加入队列,开始进行广度优先搜索。在广度优先搜索的过程中,每个搜索到的 1 都会被重新标记为 0。直到队列为空,搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数

BFs比Dfs简单点的就是不需要Dfs深搜函数 直接在一个大循环中新建队列就可以利用队列进行搜索值为1的位置并且更改其值为0 

注意:1.Queue<int[]> 存储的是 一维数组int[]),每个 int[] 存储的是一个位置的坐标(例如,二维数组中的行和列)

假设二维数组 grid 长这样:

grid = { {'1', '0', '1'}, {'0', '1', '0'}, {'1', '0', '1'} }

遍历数组后,存储到队列中的内容会是:

queue = { {0, 1}, {1, 0}, {1, 2}, {2, 1} }

每个队列元素是一个 int[] 数组,例如 {0, 1},表示二维数组 grid 中的位置 (0, 1),即 grid[0][1] 的值是 '0'

Queue也可以在外边声明也可以在if语句中声明  

2.将 Queue 的声明移到 if 语句内部的好处是: 

  1. 每次发现新的岛屿时,您都会创建一个新的队列,这样就不会重用先前岛屿的队列。
  2. 这样也可以让 queue 仅在岛屿查找过程中存在,避免了不必要的内存占用。

代码实现:

using System;
System.Collections.Generic
class Program
{
    static void Main()
    {
        //读取输入
        string[] firstLine=Console.ReadLine().Split();//读取一行输入并将其分割成一个字符串数组
        int n=int.Parse(firstLine[0]);
        int m=int.Parse(firstLine[1]);
        
        //填充岛屿
        int[,] grid=new int[n,m];
        
        for(int i=0;i<n;i++)
        {
            firstLine=Console.ReadLine().Split();
            for(int j=0;j<m;j++)     //填充每一行
            {
                grid[i,j]=int.Parse(firstLine[j]);
            }
        }
        
        //计算岛屿数量
        int Count=CountIsland(grid,n,m);
        Console.WriteLine(Count);
    }
    
    public int CountIsland(int[,]grid ,int n,int m)
    {
        int count=0;
         
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i,j]==1)
                {
                    count++;
                   grid[i,j]=0;
                   Queue<int[]> queue=new Queue<int[]>();
                  queue.Enqueue(new int[]{i,j});//将坐标入队 
                  while(queue.Count>0)
                  {
                      int[] tmp=queue.Dequeue();
                      int r=tmp[0];
                      int c=tmp[1];
                    //判断该坐标四周
                        if(r-1>=0 && grid[r-1,c]==1)
                        {
                            queue.Enqueue(new int[]{r-1,c});
                            grid[r-1,c]=0;
                        }
                        if(r+1<n && grid[r+1,c]==1)
                        {
                            queue.Enqueue(new int[]{r+1,c});
                            grid[r+1,c]=0;
                        }
                         if(c-1>=0 && grid[r,c-1]==1)
                        {
                            queue.Enqueue(new int[]{r,c-1});
                            grid[r,c-1]=0;
                        }
                         if(c+1<m && grid[r,c+1]==1)
                        {
                            queue.Enqueue(new int[]{r,c+1});
                            grid[r,c+1]=0;
                        }                 
                  }
                }
            }
        }
        return count; //返回岛屿数量
    }
    
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

本地使用conda创建django虚拟环境

1、首先本地安装好conda。 2、创建django的虚拟环境 conda create -n django # 这里的 django只是虚拟的名称&#xff0c;自己随便名字就行&#xff0c;只要你自己知道这个是django的虚拟环境就行。 3、安装成功&#xff0c;查看虚拟环境 conda env list 4、激活虚拟环境…

rabbitMQ

官网&#xff1a;https://www.rabbitmq.com/ 一 介绍与安装 1 安装 我们同样基于Docker来安装RabbitMQ&#xff0c;使用下面的命令即可&#xff1a; docker run \-e RABBITMQ_DEFAULT_USERitheima \-e RABBITMQ_DEFAULT_PASS123321 \-v mq-plugins:/plugins \--name rabbi…

reg注册表研究与物理Hack

reg注册表研究与物理Hack 声明&#xff1a;内容的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 目录 reg注册表研究与物理HackWindows注册表修改注册表实现应用程序开机…

【黑盒测试】等价类划分法及实例

本文主要介绍黑盒测试之等价类划分法&#xff0c;如什么是等价类划分法&#xff0c;以及如何划分&#xff0c;设计等价类表。以及关于三角形案例的等价类划分法。 文章目录 一、什么是等价类划分法 二、划分等价类和列出等价类表 三、确定等价类的原则 四、建立等价类表 …

适用于个人或团队的文档管理和知识库系统,NAS快速部署『BookStack』

适用于个人或团队的文档管理和知识库系统&#xff0c;NAS快速部署『BookStack』 哈喽小伙伴们好&#xff0c;我是Stark-C~ 知识库对于很多需要和文字打交道的个人或者团队都不陌生对吧&#xff1f;对于我们个人来说&#xff0c;它可以将常用的学习资料、工作笔记、项目计划和…

delphi fmx android 自动更新(一)

12.2 android10测试通过 一,安卓权限设置 1,REQUEST_INSTALL_PACKAGES 权限 2,INTERNET 权限 3,READ_EXTERNAL_STORAGE 权限 4,WRITE_EXTERNAL_STORAGE 权限 5,READ_PHONE_STATE 二,安卓下载过程 一般是从http下载安装包 apk 所以,如果是http 则,manife…

《JVM第7课》堆区

文章目录 1.概念2.指定堆大小3.新生代和老年代3.1 新生代3.2 老年代3.3 动画演示 4.分代收集理念 1.概念 堆是JVM中最重要的一块区域&#xff0c;JVM规范中规定所有的对象和数组都应该存放在堆中&#xff0c;在执行字节码指令时&#xff0c;会把创建的对象存入堆中&#xff0c…

【笔记】自动驾驶预测与决策规划_Part6_不确定性感知的决策过程

文章目录 0. 前言1. 部分观测的马尔可夫决策过程1.1 POMDP的思想以及与MDP的联系1.1.1 MDP的过程回顾1.1.2 POMDP定义1.1.3 与MDP的联系及区别POMDP 视角MDP 视角决策次数对最优解的影响 1.2 POMDP的3种常规解法1.2.1 连续状态的“Belief MDP”方法1. 信念状态的定义2. Belief …

Spring Boot框架下的知识管理与多维分类

4 系统设计 系统分析接下来的操作步骤就是系统的设计&#xff0c;这部分内容也是不能马虎对待的。因为生活都是在不断产生变化&#xff0c;人们需求也是在不断改变&#xff0c;开发技术也是在不断升级&#xff0c;所以程序也需要考虑在今后可以方便进行功能扩展&#xff0c;完成…

LeetCode17. 电话号码的字母组合(2024秋季每日一题 59)

给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits “23” 输出&#xff1a;[“…

Nature Methods | 基于流形约束的RNA速度推断精准解析细胞周期动态调节规律

生信碱移 VeloCycle算法 VeloCycle&#xff1a;基于流形约束的RNA速度推断在细胞周期动态中的精准解析 今天给各位老铁们分享一篇于2024年10月31号发表在 Nature Methods [IF: 36.1] 的文章&#xff1a;"Statistical inference with a manifold-constrained RNA velocity…

Spring挖掘:(AOP篇)

学习AOP时,我们首先来了解一下何为AOP 一. 概念 AOP&#xff08;面向切面编程&#xff0c;Aspect Oriented Programming&#xff09;是一种编程技术&#xff0c;旨在通过预编译方式或运行期动态代理实现程序功能的统一管理和增强。AOP的主要目标是在不改变原有业务逻辑代码的…

【机器学习】k最近邻分类

&#x1f4dd;本文介绍 本文为作者阅读鸢尾花书籍以及一些其他资料的k最近邻分类后&#xff0c;所作笔记 &#x1f44b;作者简介&#xff1a;一个正在积极探索的本科生 &#x1f4f1;联系方式&#xff1a;943641266(QQ) &#x1f6aa;Github地址&#xff1a;https://github.com…

《深度学习》bert自然语言处理框架

目录 一&#xff0c;关于bert框架 1、什么是bert 2、模型结构 自注意力机制&#xff1a; 3、预训练任务 4、双向性 5、微调&#xff08;Fine-tuning&#xff09; 6、表现与影响 二、Transformer 1、传统RNN网络计算时存在的问题 1&#xff09;串联 2&#xff09;并行…

开源 - Ideal库 - 常用时间转换扩展方法(一)

从事软件开发这么多年&#xff0c;平时也积累了一些方便自己快速开发的帮助类&#xff0c;一直在想着以什么方式分享出来&#xff0c;因此有了这个系列文章&#xff0c;后面我将以《开源-Ideal库》系列文章分享一些我认为比较成熟、比较方便、比较好的代码&#xff0c;如果感觉…

网络安全漏洞管理十大度量指标

前言 当前&#xff0c;网络安全漏洞所带来的风险及产生的后果&#xff0c;影响到网络空间乃至现实世界的方方面面&#xff0c;通信、金融、能源、电力、铁路、医院、水务、航空、制造业等行业各类勒索、数据泄露、供应链、钓鱼等网络安全攻击事件层出不穷。因此&#xff0c;加…

R语言*号标识显著性差异判断组间差异是否具有统计意义

前言 该R代码用于对Iris数据集进行多组比较分析&#xff0c;探讨不同鸢尾花品种在不同测量变量&#xff08;花萼和花瓣长度与宽度&#xff09;上的显著性差异。通过将数据转换为长格式&#xff0c;并利用ANOVA和Tukey检验&#xff0c;代码生成了不同品种间的显著性标记&#x…

Web前端PC端开发者工具详细介绍(约10000字保姆级讲解)

1.Elements部分 首先按下F12键即可进入开发者工具页面&#xff0c;以CSDN博客页面为例&#xff0c;如下可以看到右侧是该页面所对应的前端代码。 在Elements部分的Styles模块下可以看页面的各个类别的样式等。 &#xff08;1&#xff09;点击.cls可以开启动态修改元素的class&a…

SQL Server 日志记录

SQL Server是一个关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;旨在有效地存储、组织、检索和操作大量结构化数据。SQL Server日志是监控数据库活动、排查问题和确保数据一致性的基础&#xff0c;这些日志记录了SQL Server实例中发生的事件的时间顺序。它们充当…

Qt QCustomplot 在采集信号领域的应用

文章目录 一、常用的几种开源库:1、QCustomPlot:2、QChart:3、Qwt:QCustomplot 在采集信号领域的应用1、应用实例时域分析频谱分析2.数据筛选和处理其他参考自然界中的物理过程、传感器和传感器网络、电路和电子设备、通信系统等都是模拟信号的来源。通过可视化模拟信号,可以…