福建建设局网站wordpress主题商店
和之前的卡码网深搜版是一道题 力扣第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; //返回岛屿数量
}
}