岛屿数量 广搜版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; //返回岛屿数量
    }
    
}