和之前的卡码网深搜版是一道题 力扣第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
语句内部的好处是:
- 每次发现新的岛屿时,您都会创建一个新的队列,这样就不会重用先前岛屿的队列。
- 这样也可以让
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; //返回岛屿数量
}
}