孤岛的总面积(Dfs C#
卡码网 101题
力扣第
1254. 统计封闭岛屿的数目 也是一样的 差不多是一道题
101. 孤岛的总面积
题目描述
给定一个由 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输出示例
1提示信息
在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。
数据范围：
1 <= M, N <= 50。
看力扣题解是有很多种方法 深搜中有 用bool DFs的 也有用边长的 但是我没太看懂边长的版本
代随的方法是 先清理完四边的陆地再普通深搜搜一遍岛屿数量 然后将每个岛屿的面积相加 感觉比较清晰简单故采用这个方法
思路：先清理完四边的陆地再普通深搜搜一遍岛屿数量 然后将每个岛屿的面积相加
using System;
class Program
{
static void Main()
{
//读取输入
string[] firstLine=Console.ReadLine().Split();//读取一行输入并将其分割成一个字符串数组
int n=int.Parse(firstLine[0]);
int m=int.Parse(firstLine[1]);
//总面积
int result=0;
//填充岛屿
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 SumLand =AreaIsland(grid,n,m);
Console.WriteLine(SumLand);
}
//遍历整个数组并且将每一个岛屿的面积相加
public static int AreaIsland(int[,]grid ,int n,int m)
{
//清理上下左右边界的陆地
for(int i=0;i<m;i++)
{
if(grid[0,i]==0)//如果第一行找到土地 直接DFS全变为水
{
Dfs(grid,0,i,n,m);
}
if(grid[n-1,i]==0)
{
Dfs(grid,n-1,i,n,m);
}
}
//左右列
for(int j=0;j<n;j++)
{
if(grid[j,0]==0)//如果第一列找到土地 直接DFS全变为水
{
Dfs(grid,j,0,n,m);
}
if(grid[j,m-1]==0)
{
Dfs(grid,j,m-1,n,m);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i,j]==1)
{
int s= Dfs(grid,i,j,n,m);
result+=s; //每次循环都累加面积
}
}
}
return result; //返回岛屿总面积
}
public static int Dfs(int[,] grid ,int r,int c,int n,int m)
{
//如果下标不在范围内 直接返回
if(r<0 || r>=n ||c<0 ||c>=m)
{
return 0;
}
if(grid[r,c]!=1)
{
return 0;
}
//如果在范围内
//将当前陆地标记为水 避免重复基数
grid[r,c]=0; //递归访问四个方向
return 1+Dfs(grid,r+1,c,n,m)
+Dfs(grid,r-1,c,n,m)
+Dfs(grid,r,c+1,n,m)
+Dfs(grid,r,c-1,n,m);
}
}