第六十六天打卡 | 卡码网101 孤岛的总面积、卡码网102 沉没孤岛、卡码网103 水流问题、卡码网104 建造最大岛屿

卡码网101 孤岛的总面积


这一题在昨天的基础上,将比较得出最大孤岛面积的逻辑改为统计所有孤岛面积之和的逻辑即可。       

最近做项目的时候也发现,很多时候代码逻辑能够复用最好就不要再自己写,防止出错,当然刷代码题的时候不一定是这个样子,就先偷个懒哈

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};
 
int bfs(vector<vector<int>>& grid, vector<vector<int>>& visited, int i_index, int j_index) {
    int sum = 0;
    queue<pair<int, int>> que;
    que.push(pair<int, int>(i_index, j_index));
    bool flag = true;
    while (!que.empty()) {
        // int num = que.size();
        // while (num--) {
            i_index = que.front().first;
            j_index = que.front().second;
            for (int i = 0; i < 4; i++) {
                if (i_index + dir[i][0] >= 0 && i_index + dir[i][0] < grid.size()) {
                    if (j_index + dir[i][1] >= 0 && j_index + dir[i][1] < grid[0].size()) {
                        if (grid[i_index+dir[i][0]][j_index+dir[i][1]] && 
                        !visited[i_index+dir[i][0]][j_index+dir[i][1]]) {
                            visited[i_index+dir[i][0]][j_index+dir[i][1]] = 1;
                            if (i_index+dir[i][0] == 0 || i_index+dir[i][0] == grid.size() - 1 
                            || j_index+dir[i][1] == 0 || j_index+dir[i][1] == grid[0].size() - 1)
                            {
                                
                                flag = false; 
                            }
                            sum++;
                            que.push(pair<int, int>(i_index+dir[i][0],j_index+dir[i][1]));
                        }
                    }
                }
            }   
            que.pop();
        // }
    }
    if (flag)
        return sum + 1;
    else return 0;
}
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<int>> visited(n, vector<int>(m, 0));
    int sum = 0; 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] && !visited[i][j]) {
                visited[i][j] = 1;
                // if (sum < bfs(grid, visited, i, j))
                if (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1)
                {
                    bfs(grid, visited, i, j);   
                }
                else 
                    sum += bfs(grid, visited, i, j);
                    // cout << sum << endl;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

卡码网102 沉没孤岛


先要用一个bfs的逻辑或者一个dfs的逻辑判断是否是孤岛,即是否遍历到的横向或者纵向相连的所有节点都不和最外层边界直接触碰,这里传参数有个技巧,原本都是用的引用,这里在传入visited数组的时候不用加引用符对原visited数组进行修改,否则就是直接在遍历了。

在第二次修改孤岛的时候再用原先的visited数组加上引用就行。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};
 
 /*
  * Description: 判断是否是孤岛
  */
 
bool ifIsolated(vector<vector<int>>& grid, vector<vector<int>> visited, int i_index, int j_index) {
    queue<pair<int, int>> que;
    que.push(pair<int, int>(i_index, j_index));
    bool flag = true;
    while (!que.empty()) {
        // int num = que.size();
        // while (num--) {
            i_index = que.front().first;
            j_index = que.front().second;
            for (int i = 0; i < 4; i++) {
                if (i_index + dir[i][0] >= 0 && i_index + dir[i][0] < grid.size()) {
                    if (j_index + dir[i][1] >= 0 && j_index + dir[i][1] < grid[0].size()) {
                        if (grid[i_index+dir[i][0]][j_index+dir[i][1]] && 
                        !visited[i_index+dir[i][0]][j_index+dir[i][1]]) {
                            visited[i_index+dir[i][0]][j_index+dir[i][1]] = 1;
                            if (i_index+dir[i][0] == 0 || i_index+dir[i][0] == grid.size() - 1 
                            || j_index+dir[i][1] == 0 || j_index+dir[i][1] == grid[0].size() - 1)
                            {
                                
                                flag = false; 
                            }
                            que.push(pair<int, int>(i_index+dir[i][0],j_index+dir[i][1]));
                        }
                    }
                }
            }   
            que.pop();
        // }
    }
    return flag;
} 

/*
 * 
 * Description: 孤岛取反
 */
void bfs(vector<vector<int>>& grid, vector<vector<int>>& visited, int i_index, int j_index, bool flag) {
    if (flag) grid[i_index][j_index] = 0;
    queue<pair<int, int>> que;
    que.push(pair<int, int>(i_index, j_index));
    while (!que.empty()) {
            i_index = que.front().first;
            j_index = que.front().second;
            for (int i = 0; i < 4; i++) {
                if (i_index + dir[i][0] >= 0 && i_index + dir[i][0] < grid.size()) {
                    if (j_index + dir[i][1] >= 0 && j_index + dir[i][1] < grid[0].size()) {
                        if (grid[i_index+dir[i][0]][j_index+dir[i][1]] && 
                        !visited[i_index+dir[i][0]][j_index+dir[i][1]]) {
                            visited[i_index+dir[i][0]][j_index+dir[i][1]] = 1;
                            if (flag == true) 
                                grid[i_index+dir[i][0]][j_index+dir[i][1]] = 0;
                            que.push(pair<int, int>(i_index+dir[i][0],j_index+dir[i][1]));
                        }
                    }
                }
            }   
            que.pop();
        // }
    }
}
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<int>> visited(n, vector<int>(m, 0));
    bool flag = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] && !visited[i][j]) {
                visited[i][j] = 1;
                // if (sum < bfs(grid, visited, i, j))
                if (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1)
                {
                    flag = false;
                    bfs(grid, visited, i, j, flag);   
                }
                else {
                    flag = ifIsolated(grid, visited, i, j);
                    bfs(grid, visited, i, j, flag);   
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << grid[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

卡码网103 水流问题


训练营越到后面,其实是越来越顺的,一方面是有了动量和习惯气的支撑,另一方面也是前面的知识和编程技巧掌握了之后对于后面的解题很自然而然就用到了,所以建议前面的题目还是要认真刷,有时间的话建议也像这样子每天写个博客总结记录下,后面可以当成笔记来复习的。

这一题逻辑和前面的就比较像,可以自行进行思考尝试,这里给出我写的代码,权当抛砖引玉了

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};
 
 /*
  * Description: 判断是否是符合条件的点
  */
 
bool ifAble(vector<vector<int>>& grid, vector<vector<int>> visited, int i_index, int j_index) {
    queue<pair<int, int>> que;
    que.push(pair<int, int>(i_index, j_index));
    bool flagl_u = false;
    bool flagr_d = false;
    if (i_index == 0 ||  j_index == 0)
    {
        flagl_u = true; 
    }
    if (i_index == grid.size() - 1 || j_index == grid[0].size() - 1) {
        flagr_d = true;
    }
    if (flagl_u && flagr_d) return true;
    while (!que.empty()) {
            i_index = que.front().first;
            j_index = que.front().second;
            for (int i = 0; i < 4; i++) {
                if (i_index + dir[i][0] >= 0 && i_index + dir[i][0] < grid.size()) {
                    if (j_index + dir[i][1] >= 0 && j_index + dir[i][1] < grid[0].size()) {
                        if (grid[i_index+dir[i][0]][j_index+dir[i][1]] <= grid[i_index][j_index] &&
                        !visited[i_index+dir[i][0]][j_index+dir[i][1]]) {
                            visited[i_index+dir[i][0]][j_index+dir[i][1]] = 1;
                            if (i_index+dir[i][0] == 0 ||  j_index+dir[i][1] == 0)
                            {
                                flagl_u = true; 
                            }
                            if (i_index+dir[i][0] == grid.size() - 1 || j_index+dir[i][1] == grid[0].size() - 1) {
                                flagr_d = true;
                            }
                            if (flagl_u && flagr_d) return true;
                            que.push(pair<int, int>(i_index+dir[i][0],j_index+dir[i][1]));
                        }
                    }
                }
            }   
            que.pop();
        // }
    }
    return flagl_u && flagr_d;
} 

 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<int>> visited(n, vector<int>(m, 0));
    bool flag = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ifAble(grid, visited, i, j)) {
                cout << i << ' ' << j << endl;
            }
        }
    }
    return 0;
}

卡码网104 建造最大岛屿


(暂时没想出来,给出题解如下,可自行学习,后面再改改)

每次深搜遍历计算最大岛屿面积,都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步:一次遍历地图,得出各个岛屿的面积,并做编号记录。可以使用map记录,key为岛屿编号,value为岛屿面积

第二步:再遍历地图,遍历0的方格(因为要将0变成1),并统计该1(由0变成的1)周边岛屿面积,将其相邻面积相加在一起,遍历所有 0 之后,就可以得出 选一个0变成1 之后的最大面积。

拿如下地图的岛屿情况来举例: (1为陆地)

第一步,则遍历题目,并将岛屿到编号和面积上的统计,过程如图所示:

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {
    if (visited[x][y] || grid[x][y] == 0) return; // 终止条件:访问过的节点 或者 遇到海水
    visited[x][y] = true; // 标记访问过
    grid[x][y] = mark; // 给陆地标记新标签
    count++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了,直接跳过
        dfs(grid, visited, nextx, nexty, mark);
    }
}

int largestIsland(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); // 标记访问过的点
    unordered_map<int ,int> gridNum;
    int mark = 2; // 记录每个岛屿的编号
    bool isAllGrid = true; // 标记是否整个地图都是陆地
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 0) isAllGrid = false;
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 0;
                dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
                gridNum[mark] = count; // 记录每一个岛屿的面积
                mark++; // 记录下一个岛屿编号
            }
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/731522.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

环境配置04:Pytorch下载安装

说明&#xff1a; 显存大于4G的建议使用GPU版本的pytorch&#xff0c;低于4G建议使用CPU版本pytorch&#xff0c;直接使用命令安装对应版本即可 GPU版本的pytorch的使用需要显卡支持&#xff0c;需要先安装CUDA&#xff0c;即需要完成以下安装 1.查看已安装CUDA版本 GPU对应…

基于DPU的云原生裸金属网络解决方案

1. 方案背景和挑战 裸金属服务器是云上资源的重要部分&#xff0c;其网络需要与云上的虚拟机和容器互在同一个VPC下&#xff0c;并且能够像容器和虚拟机一样使用云的网络功能和能力。 传统的裸金属服务器使用开源的 OpenStack Ironic 组件&#xff0c;配合 OpenStack Neutron…

Uncaught TypeError: Cannot read properties of null (reading ‘isCE‘)

问题描述 使用 view-ui-plus 加 vue3 开发项目&#xff0c;本地启动项目正常&#xff0c;但其他人将代码拉下来&#xff0c;启动项目时报错 Uncaught TypeError: Cannot read properties of null (reading isCE)&#xff1a; 原因分析&#xff1a; 尝试将 mode_nodules 文件删…

量子计算:1 从薛定谔的猫开始

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调或者LLM背后的基础模型重新阅读。而最新科技&#xff08;Mamba,xLSTM,KAN&#xff09;则…

C++ 编程技巧分享

侯捷 C 学习路径&#xff1a;面向对象的高级编程 -> STL库 -> C11新特性 -> cmake 1.1. C 与 C的区别 在C语言中&#xff0c;主要存在两大类内容&#xff0c;数据和处理数据的函数&#xff0c;二者彼此分离&#xff0c;是多对多的关系。不同的函数可以调用同一个数据…

【Linux进程】手把手教你如何调整----进程优先级(什么是优先级?为什么要有优先级?)

目录 一、前言 二、优先级的基本概念 &#x1f95d; 什么是优先级&#xff1f; &#x1f34d; 为什么要有优先级&#xff1f; 三、如何查看并修改 --- 进程优先级 &#x1f347; PRI and NI &#x1f525;PRI&#x1f525; &#x1f525;NI&#x1f525; &#x1f3…

亿发开启极速开单新纪元,解锁业务新速度,提升企业竞争力

我们不断追求卓越&#xff0c;致力于通过技术革新&#xff0c;为客户带来更快捷、更智能、更全面的进销存管理体验。立即更新&#xff0c;享受更高效的业务处理流程。

A股3000点失守是出局还是机会?

今天的大A失守300点&#xff0c;那么A股3000点失守是出局还是机会&#xff1f; 1、今天两市低开&#xff0c;盘中一度跌破3000点&#xff0c;最低回踩到了2985点&#xff0c;盘面出现了两个罕见现象&#xff0c;意味着即将探底回升。 2、盘面出现两个罕见现象&#xff1a; 一是…

【嵌入式开发】UART

目录 一、概述 1.1 常见的通信类别/特点 1.2 常见几种通信 二、UART通信协议 2.1 UART通信介绍 2.2 UART通信协议 物理连接示意图&#xff1a; 三、STM32的UART接口 3.1 STM32的UART特点 3.2 STM32的UART框图分析 3.3 UART初始化步骤 3.4 STM32中UART使用 一、概述…

代码随想录第30天|贪心算法

122.买卖股票的最佳时机II 给你一个整数数组 prices &#xff0c;其中 prices[i] 表示某支股票第 i 天的价格。 在每一天&#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买&#xff0c;然后在 同一天 出售。 返回 你能获得…

Java项目:基于SSM框架实现的绿色农产品推广应用网站果蔬商城水果商城蔬菜商城【ssm+B/S架构+源码+数据库+答辩PPT+毕业论文】

一、项目简介 本项目是一套基于SSM框架实现的绿色农产品推广应用网站果蔬商城水果商城蔬菜商城 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能…

kettle无法启动问题_PENTAHO_JAVA_HOME

1&#xff0c;遇到spoon.bat启动报错&#xff1a;先增加pause看清错误信息 1.1&#xff0c;错误信息 1.2&#xff0c;因为本地安装jdk1.6无法支持现有版本kettle。只能手动执行kettle调用的java路径&#xff1b;如下 系统--高级系统设置--高级--环境变量 启动成功

【CMake】CMake从入门到实战系列(十七)—— CMake添加环境检查

&#x1f525;博客简介&#xff1a;开了几个专栏&#xff0c;针对 Linux 和 rtos 系统&#xff0c;嵌入式开发和音视频开发&#xff0c;结合多年工作经验&#xff0c;跟大家分享交流嵌入式软硬件技术、音视频技术的干货。   ✍️系列专栏&#xff1a;C/C、Linux、rtos、嵌入式…

【无线传感网】LEACH路由算法

1、LEACH路由算法简介 LEACH协议,全称是“低功耗自适应集簇分层型协议” (Low Energy Adaptive Clustering Hierarchy),是一种无线传感器网络路由协议。基于LEACH协议的算法,称为LEACH算法。 2、LEACH路由算法的基本思想 LEACH路由协议与以往的路由协议的不同之处在于其改变…

C#.net6.0语言+前端Vue,Ant-Design开发的智慧医院手术室麻醉管理平台源码 什么是手术麻醉临床信息管理系统?

C#.net6.0语言前端Vue,Ant-Design开发的智慧医院手术室麻醉管理平台源码 什么是手术麻醉临床信息管理系统&#xff1f; 手术麻醉临床信息管理系统涵盖了手术进程管理、自动排班、手术记录、术前评估与麻醉记录等功能&#xff0c;强调了系统如何通过技术架构和数据集成提高工作…

python代码生成可执行文件

以下面转换图片尺寸的代码resize_images.py为例&#xff1a; 代码功能&#xff1a;原始图片放在img文件夹中&#xff0c;然后运行代码可以转换成指定分辨率&#xff0c;保存在同一目录下的新生成的文件夹中 import os import sys import cv2 from datetime import datetime f…

第4集《大乘起信论》

请大家打开《讲义》第七页。 解释标题有别释跟合释&#xff0c;在合释当中又分两科。第一个明心&#xff0c;先明白我们内在的种性&#xff0c;这个种性就会产生不同的业力、不同的果报。在明白这个道理以后&#xff0c;我们应该怎么去扭转这个种性呢&#xff1f;就讲到修学的…

贝锐蒲公英异地组网方案:实现制药设备远程监控、远程运维

公司业务涉及放射性药品的生产与销售&#xff0c;在全国各地拥有20多个分公司。由于药品的特殊性&#xff0c;在日常生产过程中&#xff0c;需要符合药品监管规范要求&#xff0c;对各个分部的气相、液相设备及打印机等进行监管&#xff0c;了解其运行数据及工作情况。 为满足这…

MobileNet系列论文阅读笔记(MobileNetV1、MobileNetV2和MobileNetV3)

目录 引言MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications摘要Prior Work -- 先前工作MobileNet Architecture— MobileNet结构Depthwise Separable Convolution—深度可分离卷积Network Structure -- 网络结构 总结 MobileNetV2: Invert…

19 Shell编程之条件语句

目录 19.1 条件测试操作 19.1.1 文件测试 19.1.1 整数值比较 19.1.3 字符串比较 19.1.4 逻辑测试 19.2 if条件语句 19.2.1 if语句的结构 19.2.2 if语句应用示例 19.3 case分支语句 19.3.1 case语句的结构 19.3.2 case语句应用示例 19.1 条件测试操作 Shell环境根据命令执行后…