代码随想录第五十一天

🕗 发布于 2024-12-09 13:16 算法图论 数据结构 c语言 leetcode

99.岛屿数量

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例

输出示例

提示信息

数据范围：

1 <= N, M <= 50

第一种方法(深度优先搜索)

思路：

每个岛屿是由若干个相邻的 1（陆地）组成的连通区域，岛屿之间是通过上下左右相邻的陆地连接的。在实现过程中，首先会创建一个图（graph）来存储网格的值，并使用一个 path 数组来记录哪些位置已经被访问过。然后，通过逐个遍历网格中的每个位置，如果当前位置是 1 且未被访问过，就启动一次 DFS 遍历，从这个位置开始，将所有与其相连的 1 标记为已访问，这样就能找到并遍历整个岛屿。在 DFS 遍历过程中，会检查四个方向（上、下、左、右），确保每个位置都在网格的有效范围内。如果当前位置是 1 且未访问过，则继续向相邻的四个方向递归地进行 DFS 遍历，直到这个岛屿的所有陆地都被标记为已访问。每次找到一个未被访问的 1 时，就代表发现了一个新的岛屿，岛屿数量加 1。这样，最终可以统计出网格中岛屿的总数量。

解答：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 
int** graph = NULL;
bool** path = NULL;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void DFS(int** graph,bool** path,int x,int y,int M,int N)
{
    for(int i = 0;i < 4;i++)
    {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if(nextx < 0 || nextx >= M || nexty < 0 || nexty >= N)
        {
            continue;
        }
        if(!path[nextx][nexty] && graph[nextx][nexty] == 1)
        {
            path[nextx][nexty] = true;
            DFS(graph,path,nextx,nexty,M,N);
        }
    }
}
int main()
{
    int N,M;
    scanf("%d %d",&N,&M);
    graph = malloc(sizeof(int*)*N);
    for(int i = 0;i < N;i++)
    {
        graph[i] = malloc(sizeof(int)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            scanf("%d",&graph[i][j]);   
        }    
    }
    path = malloc(sizeof(bool*)*N);
    for(int i = 0;i < N;i++)
    {
        path[i] = malloc(sizeof(bool)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            path[i][j] = false;
        }
    }
    int count = 0;
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if(graph[i][j] == 1 && !path[i][j])
            {
                path[i][j] = true;
                DFS(graph,path,i,j,N,M);
                count++;
            }
        }
    }
    printf("%d",count);
    return 0;
}

第二种方法(广度优先搜索)

思路：

首先，我们使用一个队列来存储待访问的节点，每次从队列中取出一个节点，并检查其四个方向（右、下、左、上）。对于每一个方向，若相邻的节点是陆地且未被访问过，就将该节点加入队列，并标记为已访问。这样，队列会不断扩展，直到岛屿中的所有陆地都被访问过。每当我们找到一个未被访问的陆地时，说明我们发现了一个新岛屿，因此开始新的 BFS 遍历，直到所有的岛屿都被标记完。在 main 函数中，我们读取输入网格，初始化 graph 和 path 数组，并在网格中每遇到一个未访问的陆地时调用 BFS，最终计算岛屿的总数。

解答：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 
#define queue_node 1000
int queuex[queue_node];
int queuey[queue_node];
int front = 0;
int rear = 0;
int** graph = NULL;
bool** path = NULL;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int empty()
{
    return rear == front;    
}
void enqueue(int x,int y)
{
    queuex[rear] = x;
    queuey[rear] = y;
    rear++;
}
void popqueue(int* x,int* y)
{
    *x = queuex[front];
    *y = queuey[front];
    front++;
}
void BFS(int** graph,bool** path,int x,int y,int M,int N)
{
    enqueue(x,y);
    path[x][y] = true;
    while(!empty())
    {
        int X,Y;
        popqueue(&X,&Y);
        for(int i = 0;i < 4;i++)
        {
            int nextx = X + dir[i][0];
            int nexty = Y + dir[i][1];
            if(nextx < 0 || nextx >= N || nexty < 0 || nexty >= M)
            {
                continue;
            }
            if(!path[nextx][nexty] && graph[nextx][nexty] == 1)
            {
                enqueue(nextx,nexty);
                path[nextx][nexty] = true;
            }
        }
    }
}
int main()
{
    int N,M;
    scanf("%d %d",&N,&M);
    graph = malloc(sizeof(int*)*N);
    for(int i = 0;i < N;i++)
    {
        graph[i] = malloc(sizeof(int)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            scanf("%d",&graph[i][j]);   
        }    
    }
    path = malloc(sizeof(bool*)*N);
    for(int i = 0;i < N;i++)
    {
        path[i] = malloc(sizeof(bool)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            path[i][j] = false;
        }
    }
    int count = 0;
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if(graph[i][j] == 1 && !path[i][j])
            {
                count++;
                BFS(graph,path,i,j,M,N);
            }
        }
    }
    printf("%d",count);
    return 0;
}

100.岛屿的最大面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

输出示例

提示信息

数据范围：

1 <= M, N <= 50。

思路：

首先，我们读取输入的二维地图，它由 1 和 0 组成，1 表示陆地，0 表示水域。然后，我们使用一个 path 数组来标记每个位置是否被访问过。程序从每个未访问的陆地（即 graph[i][j] == 1）开始执行 BFS，每当找到一个新的岛屿时，我们便计算该岛屿的面积。BFS 算法通过队列来逐层遍历岛屿，队列中的元素是一个个位置，每次我们从队列中弹出一个位置，并检查其四个方向的相邻位置（上下左右），若相邻位置是 1 且未被访问，则将其加入队列，继续扩展。对于每个岛屿，我们统计其面积，也就是计算 BFS 遍历到的 1 的个数。每次 BFS 结束后，更新最大岛屿面积，最终遍历完所有的点，程序将输出最大的岛屿面积。在实现时，队列用于存储待处理的陆地位置，队列的入队和出队操作确保了广度优先的顺序。每当处理完一个岛屿后，我们会清除已访问的标记，继续处理下一个未访问的陆地，直到所有的点都被遍历过为止。这样，最终我们能够找到并返回最大岛屿的面积。

解答：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define queue_node 1000
int queuex[queue_node];
int queuey[queue_node];
int** graph = NULL;
bool** path = NULL;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int front = 0;
int rear = 0;
int count;
int empty()
{
    return rear == front;
}
void enqueue(int x,int y)
{
    queuex[rear] = x;
    queuey[rear] = y;
    rear++;
}
void popqueue(int* x,int* y)
{
    *x = queuex[front];
    *y = queuey[front];
    front++;
}
int BFS(int** graph,bool** path,int x,int y,int M,int N)
{
    enqueue(x,y);
    path[x][y] = true;
    while(!empty())
    {
        int curx,cury;
        popqueue(&curx,&cury);
        for(int i = 0;i < 4;i++)
        {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if(nextx < 0 || nextx >= N || nexty < 0 || nexty >= M)
            {
                continue;
            }
            if(!path[nextx][nexty] && graph[nextx][nexty] == 1)
            {
                enqueue(nextx,nexty);
                count++;
                path[nextx][nexty] = true;
            }
        }
    }
    return count;
}
int main()
{
    int N,M;
    scanf("%d %d",&N,&M);
    graph = malloc(sizeof(int*)*N);
    for(int i = 0;i < N;i++)
    {
        graph[i] = malloc(sizeof(int)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            scanf("%d",&graph[i][j]);   
        }    
    }
    path = malloc(sizeof(bool*)*N);
    for(int i = 0;i < N;i++)
    {
        path[i] = malloc(sizeof(bool)*M);
    }
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            path[i][j] = false;
        }
    }
    int max_result = 0;
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if(graph[i][j] == 1 && !path[i][j])
            {
                count = 1;
                int result = BFS(graph,path,i,j,M,N);
                if(max_result < result)
                {
                    max_result = result;
                }
            }
        }
    }
    printf("%d",max_result);
    return 0;
}

反思：

今天的题目都还好，都还是比较好懂的，对于深度优先搜索和广度优先搜索都有了一定的思考和认识。

原文地址：https://blog.csdn.net/2301_80630236/article/details/144276388

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Python进阶教程：从基础到进阶
下一篇：【设计模式系列】策略模式（二十四）

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

代码随想录第五十一天

99.岛屿数量

100.岛屿的最大面积

反思：

相关文章