代码随想录第51天

99.岛屿数量 深搜

import java.util.*;

class Main{
    static int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static boolean[][] visited;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[][] grids = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                grids[i][j] = sc.nextInt();
            }
        }
        
        int cnt = 0;
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grids[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    dfs(grids, i, j);
                }
            }
        }
        System.out.println(cnt);
    }
    
    private static void dfs(int[][] grids, int x, int y) {
        visited[x][y] = true;
        for(int i = 0; i < 4; i++) {
            int nextX = x + directions[i][0];
            int nextY = y + directions[i][1];
            if(check(grids, nextX, nextY)) {
                dfs(grids, nextX, nextY);
            }
        }
    }
    
    private static boolean check(int[][] grids, int x, int y) {
        int n = grids.length;
        int m = grids[0].length;
        return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y] && grids[x][y] == 1;
    }
}

99.岛屿数量 广搜

import java.util.*;

// dfs
class Main {
    public static void main (String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] island = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                island[i][j] = sc.nextInt();
            }
        }
        int result = main.getIslandNum(island);
        System.out.println(result);
    }
    
    public int getIslandNum(int[][] island) {
        int numsIsland = 0;
        int row = island.length;
        int col = island[0].length;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (island[i][j] == 1) {
                    ++numsIsland;
                    dfs(island, i, j);
                }
            }
        }
        return numsIsland;
    }
    
    public void dfs(int[][] island, int x, int y) {
        int row = island.length;
        int col = island[0].length;
        if (x < 0 || y < 0 || x >= row || y >= col || island[x][y] == 0) {
            return;
        }
        island[x][y] = 0; // 标记为已经访问
        
        dfs(island, x, y + 1);
        dfs(island, x, y - 1);
        dfs(island, x + 1, y);
        dfs(island, x - 1, y);
    }
}

100.岛屿的最大面积

#include <stdio.h>
#include <stdlib.h>

// 四方向向量 下 右 上 左(逆时针)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int bfs(int **G, int N, int M, int x, int y);

int main(void) {
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 创建N行M列矩阵
    int **G = (int **)calloc(N, sizeof(int *));
    for(int i = 0; i < N; ++ i) {
        G[i] = (int *)calloc(M, sizeof(int));
        for(int j = 0; j < M; ++ j) {
            scanf("%d", &G[i][j]);
        }
    }
    
    // DFS函数
    int max = 0;
    int curMax;
    for(int i = 0; i < N; ++ i) {
        for(int j = 0; j < M; ++ j) {
            if (G[i][j]) {
                G[i][j] = 0;
                curMax = bfs(G, N, M, i, j);
                max = max < curMax ? curMax : max;
            }
        }
    }
    printf("%d\n", max);
    
    // 释放内存
    for(int i = 0; i < N; ++ i) free(G[i]);
    free(G);
    return 0;
}

int bfs(int **G, int N, int M, int x, int y) {
    int queue[500][2];
    int front = 0, rear = 0;
    queue[rear][0] = x;
    queue[rear ++][1] = y;
    
    int curx, cury;
    int res = 1;
    while(front < rear) {
        curx = queue[front][0];
        cury = queue[front ++][1];
        for(int i = 0; i < 4; ++ i) {
            int nextx = curx + dx[i];
            int nexty = cury + dy[i];
            if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < M) {
                if (G[nextx][nexty]) {
                    G[nextx][nexty] = 0;
                    ++ res;
                    queue[rear][0] = nextx;
                    queue[rear ++][1] = nexty;
                }
            }
        }
    }
    return res;
}

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

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

相关文章

电商数据采集电商,行业数据分析,平台数据获取|稳定的API接口数据

电商数据采集可以通过多种方式完成&#xff0c;其中包括人工采集、使用电商平台提供的API接口、以及利用爬虫技术等自动化工具。以下是一些常用的电商数据采集方法&#xff1a; 人工采集&#xff1a;人工采集主要是通过基本的“复制粘贴”的方式在电商平台上进行数据的收集&am…

PostgreSQL和Postgis安装

Windows下PostgreSQL和对应的版本的Postgis安装 PostgreSQL安装 1、官网下载地址 https://www.enterprisedb.com/downloads/postgres-postgresql-downloads 2、根据自己的系统下载完成&#xff0c;Windows下可以直接傻瓜式安装就OK 建议不要通过自带的这个程序安装postgis,…

代码开发相关操作

使用Vue项目管理器创建项目&#xff1a;&#xff08;vue脚手架安装一次就可以全局使用&#xff09; windowR打开命令窗口&#xff0c;输入vue ui&#xff0c;进入GUI页面&#xff0c;点击创建-> 设置项目名称&#xff0c;在初始化git下面输入&#xff1a;init project&…

Vulnhub DC-6靶机攻击实战(一)

导语   之前的分享中我们介绍了关于Vulnhub虚拟机前五个机器的攻防演练测试,接下来我们继续分享Vulnhub DC-6靶机攻击实战。 文章目录 搭建测试环境第一步、信息采集第二步、wpscan爆破第三步、开始查找其他的用户第四步、提权总结搭建测试环境 首先需要从Vulnhub官网中下载…

深度学习之超分辨率算法——FRCNN

– 对之前SRCNN算法的改进 输出层采用转置卷积层放大尺寸&#xff0c;这样可以直接将低分辨率图片输入模型中&#xff0c;解决了输入尺度问题。改变特征维数&#xff0c;使用更小的卷积核和使用更多的映射层。卷积核更小&#xff0c;加入了更多的激活层。共享其中的映射层&…

深度学习从入门到精通——图像分割实战DeeplabV3

DeeplabV3算法 参数配置关于数据集的配置训练集参数 数据预处理模块DataSet构建模块测试一下数据集去正则化模型加载模块DeepLABV3 参数配置 关于数据集的配置 parser argparse.ArgumentParser()# Datset Optionsparser.add_argument("--data_root", typestr, defa…

大数据操作实验一

1.Postgresql 1.1 数据库的对象创建 1.1.1 创建数据库(Database) 鼠标右键database进行创建 1.1.2 创建图(Schema) 鼠标右键schema&#xff0c;然后创建schema图纸 1.1.3 创建表(Table) 鼠标右键Table&#xff0c;创建表 1.2数据库实列化 1.2.1 实列化静态数据 提…

IDEA2024如何创建一个普通的Java Web项目工程(JSP)

本章教程,主要介绍如何在IDEA2024 专业版本中,创建一个普通的Java Web项目。 一、新建项目 二、配置项目 依次点击File——Project Structure——Modules 修改路径中的web为webapp,然后点击Create Artifact默认保存。 至此,一个基础的Java web就创建完成了。

Linux下mysql 8.0安装教程

本文介绍了如何在Linux下安装MySQL8.0,供大家参考,具体内容如下 准备工作: mysql8.0 rpm文件 测试工具(比如 idea的database工具) 安装步骤: 1. 下载mysql的repo源,下载地址: 进入Linux系统,输入指令: 1 wgethttps://dev.mysql.com/get/mysql80-community-rele…

libaom 源码分析:熵编码模块介绍

AV1 熵编码原理介绍 关于AV1 熵编码原理介绍可以参考:AV1 编码标准熵编码技术概述libaom 熵编码相关源码介绍 函数流程图 核心函数介绍 av1_pack_bitstream 函数:该函数负责将编码后的数据打包成符合 AV1 标准的比特流格式;包括写入序列头 OBU 的函数 av1_write_obu_header…

[数据结构#1] 并查集 | FindRoot | Union | 优化 | 应用

目录 1. 并查集原理 问题背景 名称与编号映射 数据结构设计 2. 并查集基本操作 (1) 初始化 (2) 查询根节点 (FindRoot) (3) 合并集合 (Union) (4) 集合操作总结 并查集优化 (1) 路径压缩 (2) 按秩合并 3. 并查集的应用 (1) 统计省份数量 (2) 判断等式方程是否成…

Centos创建共享文件夹拉取文件

1.打开VMware程序&#xff0c;鼠标右检你的虚拟机&#xff0c;打开设置 2.点击选项——共享文件夹——总是启用 点击添加&#xff0c;设置你想要共享的文件夹在pc上的路径&#xff08;我这里已经添加过了就不加了&#xff09; 注意不要中文&#xff0c;建议用share&#xff0c…

Element@2.15.14-tree checkStrictly 状态实现父项联动子项,实现节点自定义编辑、新增、删除功能

背景&#xff1a;现在有一个新需求&#xff0c;需要借助树结构来实现词库的分类管理&#xff0c;树的节点是不同的分类&#xff0c;不同的分类可以有自己的词库&#xff0c;所以父子节点是互不影响的&#xff1b;同样为了选择的方便性&#xff0c;提出了新需求&#xff0c;选择…

java版电子招投标采购|投标|评标|竞标|邀标|评审招投标系统源码

招投标管理系统是一款适用于招标代理、政府采购、企业采购和工程交易等领域的企业级应用平台。该平台以项目为主线&#xff0c;从项目立项到项目归档&#xff0c;实现了全流程的高效沟通和协作。通过该平台&#xff0c;用户可以实时共享项目数据信息&#xff0c;实现规范化管理…

【Verilog HDL 入门教程】 —— 学长带你学Verilog(基础篇)

文章目录 一、Verilog HDL 概述1、Verilog HDL 是什么2、Verilog HDL产生的背景3、Verilog HDL 和 VHDL的区别 二、Verilog HDL 基础知识1、Verilog HDL 语言要素1.1、命名规则1.2、注释符1.3、关键字1.4、数值1.4.1、整数及其表示1.4.2、实数及其表示1.4.3、字符串及其表示 2、…

龙迅#LT7911E适用于EDP/DP/TPYE-C转MIPIDSI应用,支持图像处理功能,内置I2C,主应用副屏显示,投屏领域!

1. 描述 LT7911E 是一款高性能 eDP 转 MIPI D-PHY 转换器&#xff0c;旨在将 eDP 源连接到 MIPI 显示面板。 LT7911E 集成了一个符合 eDP1.4 标准的接收器&#xff0c;支持 1.62Gbps 至 5.67Gbps 的输入数据&#xff0c;以 270Mbps 的递增步长&#xff0c;以及一个 2 端口 D…

《算法SM9》题目

判断题 SM9密码算法系统参数由KGC选择。 A.正确 B.错误 正确答案A 多项选择题 SM9密码算法KGC是负责&#xff08; &#xff09;的可信机构。 A.选择系统参数 B.生成主密钥 C.生成用户标识 D.生成用户私钥 正确答案ABD 判断题 SM9密钥封装机制封装的秘密密钥是根据…

C语言——实现求出最大值

问题描述&#xff1a;利用C语言自定义函数求出一维数组里边最大的数字 //利用函数找最大数#include<stdio.h>int search(int s[9]) //查找函数 {int i , max s[0] , max_xia 0;for(i0;i<9;i){if(s[i] > max){max_xia i;max s[max_xia];}}return max; } in…

【尚硅谷 - SSM+SpringBoot+SpringSecurity框架整合项目 】项目打包并且本地部署

前后端分离开发&#xff1a;把一个项目拆成两部分进行开发&#xff0c;所以在打包的时候&#xff0c;需要使用不同的打包方式。 后端 – SpringBoot – jar包 前端 – Vue: 因为使用了vue-admin-template框架&#xff1a;所以先使用框架进行打包使用Nginx部署&#xff0c;通…

【SH】Ubuntu Server 24服务器搭建MySQL数据库研发笔记

文章目录 搭建服务器在线安装1. 更新软件包列表2. 安装MySQL3. 检查MySQL状态4. 修改密码5. 新增用户6. 设置局域网访问 离线安装下载安装包 常用命令参考文档在线安装日志 搭建服务器 作者羊大侠搭建的是 Ubuntu Server 24.04 LTS 服务器环境 搭建参考文档&#xff1a;【SH】…