《代码随想录》刷题打卡day44:图论-part02

作者:Coder-magician日期:2026/10/1

文章目录

        • 【99.计数孤岛】
          * * DFS版本
          * BFS版本
          * 【100.岛屿的最大面积】
          * * DFS写法
          * BFS写法
【99.计数孤岛】

思路:

用遇到一个没有遍历过的节点陆地,计数器就加一,然后把该节点陆地所能遍历到的陆地都标记上。

在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

DFS版本
1# include <iostream>
2# include <vector>
3
4using namespace std;
5
6int dir[4][2] = {0,1,1,0,0,-1,-1,0}; // 四个方向
7void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
8    for(int i = 0; i < 4; i++){
9        int nextx = x + dir[i][0];
10        int nexty = y + dir[i][1];
11        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
12        // 越界了直接跳过
13        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
14
15            visited[nextx][nexty] = true;
16            dfs(grid, visited, nextx, nexty);
17        }
18    }
19}
20
21int main(){
22    int n, m;
23    cin >> n >> m;
24    vector<vector<int>> grid(n, vector<int>(m, 0));
25    vector<vector<bool>> visited(n, vector<bool>(m, false));
26
27    for(int i = 0; i < n; i++){
28        for(int j = 0; j < m; j++){
29            cin >> grid[i][j];
30        }
31    }
32
33    int result = 0;
34    for(int i = 0; i < n; i++){
35        for(int j = 0; j < m; j++){
36            if(!visited[i][j] && grid[i][j] == 1){
37                visited[i][j] = true;
38                result ++;
39                dfs(grid, visited, i, j);
40            }
41        }
42    }
43    
44    cout << result << endl;
45    return 0;
46}
47
BFS版本

这里有一个广搜中很重要的细节:

根本原因是只要 加入队列就代表 走过,就需要标记,而不是从队列拿出来的时候再去标记走过。

区别在哪里?

如果从队列拿出节点,再去标记这个节点走过,就会发生下图所示的结果,会导致很多节点重复加入队列。

超时写法 (从队列中取出节点再标记,注意代码注释的地方)

1int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
2void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
3    queue<pair<int, int>> que;
4    que.push({x, y});
5    while(!que.empty()) {
6        pair<int ,int> cur = que.front(); que.pop();
7        int curx = cur.first;
8        int cury = cur.second;
9        visited[curx][cury] = true; // 从队列中取出在标记走过
10        for (int i = 0; i < 4; i++) {
11            int nextx = curx + dir[i][0];
12            int nexty = cury + dir[i][1];
13            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了,直接跳过
14            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
15                que.push({nextx, nexty});
16            }
17        }
18    }
19
20}
21

加入队列 就代表走过,立刻标记,正确写法: (注意代码注释的地方)

1int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
2void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
3    queue<pair<int, int>> que;
4    que.push({x, y});
5    visited[x][y] = true; // 只要加入队列,立刻标记
6    while(!que.empty()) {
7        pair<int ,int> cur = que.front(); que.pop();
8        int curx = cur.first;
9        int cury = cur.second;
10        for (int i = 0; i < 4; i++) {
11            int nextx = curx + dir[i][0];
12            int nexty = cury + dir[i][1];
13            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了,直接跳过
14            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
15                que.push({nextx, nexty});
16                visited[nextx][nexty] = true; // 只要加入队列立刻标记
17            }
18        }
19    }
20
21}
22

以上两个版本其实,其实只有细微区别,就是 visited[x][y] = true; 放在的地方,这取决于我们对 代码中队列的定义,队列中的节点就表示已经走过的节点。 所以只要加入队列,立即标记该节点走过。


1# include <iostream>
2# include <vector>
3# include <queue>
4
5using namespace std;
6
7int dir[4][2] = {0,1,1,0,0,-1,-1,0}; // 四个方向
8void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
9    queue<pair<int, int>> que;
10    que.push({x, y});
11    visited[x][y] = true; // 只要加入队列,立即做标记
12    while(!que.empty()){
13        pair<int, int> cur = que.front(); que.pop();
14        int curx = cur.first;
15        int cury = cur.second;
16        for(int i = 0; i < 4; i++){
17            int nextx = curx + dir[i][0];
18            int nexty = cury + dir[i][1];
19            if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
20            if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
21                que.push({nextx, nexty});
22                visited[nextx][nexty] = true; // 只要加入队列,立即做标记
23            }
24        }
25    }
26}
27
28int main(){
29    int n, m;
30    cin >> n >> m;
31    vector<vector<int>> grid(n, vector<int>(m, 0));
32    vector<vector<bool>> visited(n, vector<bool>(m, false));
33
34    for(int i = 0; i < n; i++){
35        for(int j = 0; j < m; j++){
36            cin >> grid[i][j];
37        }
38    }
39
40    int result = 0;
41    for(int i = 0; i < n; i++){
42        for(int j = 0; j < m; j++){
43            if(!visited[i][j] && grid[i][j] == 1){
44                result++;
45                bfs(grid, visited, i, j);
46            }
47        }
48    }
49
50    cout << result << endl;
51    return 0;
52}
53
【100.岛屿的最大面积】
DFS写法
1# include <iostream>
2# include <vector>
3
4using namespace std;
5
6int count = 0;
7int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
8void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
9    for(int i = 0; i < 4; i++){
10        int nextx = x + dir[i][0];
11        int nexty = y + dir[i][1];
12        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
13        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
14
15            visited[nextx][nexty] = true;
16            count ++;
17            dfs(grid, visited, nextx, nexty);
18        }
19    }
20}
21
22int main(){
23    int n, m;
24    cin >> n >> m;
25    vector<vector<int>> grid(n, vector<int>(m, 0));
26    vector<vector<bool>> visited(n, vector<bool>(m, false));
27
28    for(int i = 0; i < n; i++){
29        for(int j = 0; j < m; j++){
30            cin >> grid[i][j];
31        }
32    }
33    int result = 0;
34    for(int i = 0; i < n; i++){
35        for(int j = 0; j < m; j++){
36            if(!visited[i][j] && grid[i][j] == 1){
37                visited[i][j] = true;
38                count = 1;
39                dfs(grid, visited, i, j);
40                result = max(result, count);
41            }
42        }
43    }
44    cout << result << endl;
45    return 0;
46}
47

BFS写法
1# include <iostream>
2# include <vector>
3# include <queue>
4
5using namespace std;
6
7int count = 0;
8int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
9void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
10    queue<pair<int, int>> que;
11    que.push({x, y});
12    visited[x][y] = true;
13    count++;
14    while(!que.empty()){
15        pair<int, int> cur = que.front(); que.pop();
16        int curx = cur.first;
17        int cury = cur.second;
18        for(int i = 0; i < 4; i++){
19            int nextx = curx + dir[i][0];
20            int nexty = cury + dir[i][1];
21            if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
22            if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
23                que.push({nextx, nexty});
24                visited[nextx][nexty] = true;
25                count++;
26            }
27        }
28    }
29}
30
31int main(){
32    int n, m;
33    cin >> n >> m;
34    vector<vector<int>> grid(n, vector<int>(m, 0));
35    vector<vector<bool>> visited(n, vector<bool>(m, false));
36
37    for(int i = 0; i < n; i++){
38        for(int j = 0; j < m; j++){
39            cin >> grid[i][j];
40        }
41    }
42    int result = 0;
43    for(int i = 0; i < n; i++){
44        for(int j = 0; j < m; j++){
45            if(!visited[i][j] && grid[i][j] == 1){
46                count = 0;
47                bfs(grid, visited, i, j);
48                result = max(result, count);
49            }
50        }
51    }
52    cout << result << endl;
53    return 0;
54}
55

《《代码随想录》刷题打卡day44:图论-part02》 是转载文章,点击查看原文。


相关推荐


綦江烟草系统学习
ZDN_is_beauty2026/9/25

一.一个系统由哪几块组成 前端画界面 + 收集用户操作后端处理业务逻辑 + 调数据库 + 调算法数据库存取数据算法专门算风险分 API(接口) 定义:前端和后端之间的约定。前端说"我要什么",后端说"给你什么"。 这个项目里:后端定义了 40 多个 API,比如: POST /api/auth/login —— 登录 GET /api/results/b —— 查 B 端结果 POST /api/tasks —— 创建算法任务 类比:菜单。服务员(前端)照着菜单(


【AI大模型接入SDK】LLMManager架构设计与实现
艾莉丝努力练剑2026/9/17

🎬 个人主页:艾莉丝努力练剑 ❄专栏传送门:《C语言》《数据结构与算法》《C/C++干货分享&学习过程记录》 《Linux操作系统编程详解》《笔试/面试常见算法:从基础到进阶》《Python干货分享》 ⭐️为天地立心,为生民立命,为往圣继绝学,为万世开太平 🎬 艾莉丝的简介: 文章目录 1 ~> 项目背景与设计目标1.1 现有模型接入方案1.2 现有方案存在的问题1.3 LLMManager 设计目标 2 ~> 核心抽象与数据结构2.1 LL


2024上半年,零售行业三大观察
2601_962099082026/9/9

字数:1563;阅读时间:4分钟 宏观层面增长放缓 将目光投至2024年上半年, 零售业相关数据有了体现, 增长速度变缓的景象慢慢明晰起来, 逐一被揭晓呈显出, 并且渐次清晰可见。 以国家统计局所给出的数据来看, 社会消费品零售总额尽管呈现出保持增长的态势, 不过, 其增速显著地放缓了, 同比增长为3.7%, 那么, 这一数字背后隐匿着零售业的哪些秘密呢? 不同零售业态的表现呈现出分化的态势。 便利店的零售额增长速度, 与专业店以及超市有所不同。其中, 便利店同比增长率以5.8%占


2.django - 项目结构和模板语法
Aa123456789_552026/9/1

静态文件要放在app/static目录中。Django会自动在这个文件中寻找对应模板 模板语法 本质上是django专属在HTML中的一些占位符。 list 取值 索引取值: 通过 “.”+索引 For循环取值 Dict字典取值 通过索引取值 获取所有key值。N3.keys 获取所有value值. N3.values 获取key和value值. N3.items 判断语句


深入理解 TCP 协议(二):TCP 可靠传输与高效通信机制详解
Mortalbreeze2026/8/24

目录 前言 一、确认应答机制 二、超时重传机制 2.1 理解丢包的本质 2.2 超时时间如何确定 三、滑动窗口机制 3.1 深度理解 send/write 和发送缓冲区 3.2 理解滑动窗口 3.3 理解结合滑动窗口发送报文的流程 3.4 滑动窗口机制的进一步理解——发送缓冲区的空间复用 3.5 滑动窗口机制的进一步优化——快速重传机制 3.6 滑动窗口的大小如何确定 四、流量控制机制 4.1 零窗口探测 4.2 16 位窗口大小的限制与窗口扩大因子 五、拥塞


如何使用GSAP实现一个 `pinned` 滚动楼层叙事?
Mh2026/8/11

准备工作 技术栈: vue + gsap 最近在做的一个动画,特意去网上查了一下叫 pinned 滚动叙事,感觉蛮有趣,分享给你们。 实现的动画如下: 对应的模仿网址是:www.vaporesso.com/series-prod… 思考过程🤔 多滚动几次上面的动画,感官上大致可以得出一个粗浅的感受。 页面滚到某一段时,画面突然停住了。你继续滚动,页面没有向下走,而是像一条时间线一样开始播放:卡片移动到中心、放大、图片和文字拉开距离,然后卡片退场,背后的内容一层一层覆盖进来。等这一段讲完,卡片


06|眼睛:LLM 的「视野」怎么拼出来,又怎么不爆
浪遏2026/8/2

这是《Agent全栈实战》的第 6 篇。整个系列以 catbuddy(一个本地优先的 AI 编程助手,约 3.6 万行 TypeScript)为案例,由浅入深拆解 harness 设计。前面我们讲了心脏(Agent Loop)和手脚(工具系统)。这一篇聊「眼睛」——模型每次开口之前,它到底看到了什么。你给 LLM 的那一长串 messages,不是随手拼的,而是一条五层流水线装出来的;而对话一长,这串东西就会撑爆上下文窗口,撞上窗口红线直接 context_length_exceeded。所以这


Java Jetty 实战详解:从嵌入式 HTTP 服务到 Spring Boot 容器替换
唐青枫2026/7/25

简介 Jetty 是 Eclipse 基金会维护的 Java Web 服务器,也是一个 Servlet 容器。 它主要能做这些事: 监听 HTTP 端口 处理 HTTP 请求和响应 运行 Servlet / Filter / Listener 部署 WAR 包 支持 WebSocket、HTTP/2、HTTP/3 作为库嵌入到 Java 程序里启动 作为 Spring Boot 的内嵌容器 一句话概括: Jetty 既能像 Tomcat 一样单独部署 Web 应用,也能像普通 Java 库一样


学习 OpenMontage 的工具发现与打分选择器
日习一技2026/7/17

在前面的几篇文章里,我们已经体验了 OpenMontage 的零成本玩法:用 Piper 配音、用免费素材剪纪录片、用 Remotion 把图片做成动画,全程不花一分钱 API 费用。我们也试过贴一个参考视频,让 agent 帮我们拆解出差异化的制作方案。 不过零成本路径终究有上限。想要 FLUX 的图、Veo 或 Kling 的真实运动镜头、ElevenLabs 的高质量配音,就得接入对应的 provider。OpenMontage 支持的 provider 有几十个,同一个能力往往有好几个、


LeetCode 28. 找出字符串中第一个匹配项的下标
Best_Jerry2026/7/9

leetcode.cn/problems/fi… programmercarl.com/0028.%E5%AE… 给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 ****。   示例 1: 输入: haystack = "sadbutsad", needle = "sad" 输出: 0 解释: "sad" 在下标 0 和

首页编辑器站点地图

本站内容在 CC BY-SA 4.0 协议下发布

Copyright © 2026 聚合阅读