济宁做网站的电话,东莞市公租房申请网站-建设网,东莞市建设企业网站企业,东莞网站优化科技有限公司和之前的卡码网深搜版是一道题 力扣第200题
99. 岛屿数量
题目描述
给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成#xff0c;并且四周都是水域。…和之前的卡码网深搜版是一道题 力扣第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.Queueint[] 存储的是 一维数组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 语句内部的好处是
每次发现新的岛屿时您都会创建一个新的队列这样就不会重用先前岛屿的队列。这样也可以让 queue 仅在岛屿查找过程中存在避免了不必要的内存占用。
代码实现
using System; System.Collections.Generic class Program { static void Main() { //读取输入 string[] firstLineConsole.ReadLine().Split();//读取一行输入并将其分割成一个字符串数组 int nint.Parse(firstLine[0]); int mint.Parse(firstLine[1]); //填充岛屿 int[,] gridnew int[n,m]; for(int i0;in;i) { firstLineConsole.ReadLine().Split(); for(int j0;jm;j) //填充每一行 { grid[i,j]int.Parse(firstLine[j]); } } //计算岛屿数量 int CountCountIsland(grid,n,m); Console.WriteLine(Count); } public int CountIsland(int[,]grid ,int n,int m) { int count0; for(int i0;in;i) { for(int j0;jm;j) { if(grid[i,j]1) { count; grid[i,j]0; Queueint[] queuenew Queueint[](); queue.Enqueue(new int[]{i,j});//将坐标入队 while(queue.Count0) { int[] tmpqueue.Dequeue(); int rtmp[0]; int ctmp[1]; //判断该坐标四周 if(r-10 grid[r-1,c]1) { queue.Enqueue(new int[]{r-1,c}); grid[r-1,c]0; } if(r1n grid[r1,c]1) { queue.Enqueue(new int[]{r1,c}); grid[r1,c]0; } if(c-10 grid[r,c-1]1) { queue.Enqueue(new int[]{r,c-1}); grid[r,c-1]0; } if(c1m grid[r,c1]1) { queue.Enqueue(new int[]{r,c1}); grid[r,c1]0; } } } } } return count; //返回岛屿数量 } }
