【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

需强化知识点

  • 103,104 优化思路

题目

101. 孤岛的总面积

  • 此处 area 多余
def dfs(grid, x, y, area):
    dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    m, n = len(grid), len(grid[0])
    area[0] += 1
    grid[x][y] = 0
    
    for add_x, add_y in dirs:
        next_x, next_y = x + add_x, y + add_y
        if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
            continue
        if grid[next_x][next_y]:
            dfs(grid, next_x, next_y, area)

tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]

for i in range(m):
    tmp = list(map(int, input().split()))
    for j in range(n):
        grid[i][j] = tmp[j]

for i in range(m):
    if grid[i][0]:
        dfs(grid, i, 0, [0])
    if grid[i][n-1]:
        dfs(grid, i, n-1, [0])
        
for j in range(n):
    if grid[0][j]:
        dfs(grid, 0, j, [0])
    if grid[m-1][j]:
        dfs(grid, m-1, j, [0])
        
cur = 0
for i in range(m):
    for j in range(n):
        if grid[i][j]:
            cur += 1

print(cur)          

102. 沉没孤岛

  • 思路:从左右上下边界出发遍历,然后visited数组标记,最后 grid 为 1 且没被访问过的,即为孤岛
import collections

def bfs(grid, visited, x, y):
    dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    m, n = len(grid), len(grid[0])
    
    que = collections.deque()
    que.append([x, y])
    visited[x][y] = True
    
    while que:
        tmp = que.popleft()
        cur_x, cur_y = tmp[0], tmp[1]
    
        for add_x, add_y in dirs:
            next_x, next_y = cur_x + add_x, cur_y + add_y
            if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
                continue
            if grid[next_x][next_y] and not visited[next_x][next_y]:
                que.append([next_x, next_y])
                visited[next_x][next_y] = True

tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]
visited = [[False] * n for _ in range(m)]

for i in range(m):
    tmp = list(map(int, input().split()))
    for j in range(n):
        grid[i][j] = tmp[j]

for i in range(m):
    if grid[i][0]:
        bfs(grid, visited ,i, 0)
    if grid[i][n-1]:
        bfs(grid, visited, i, n-1)
        
for j in range(n):
    if grid[0][j]:
        bfs(grid, visited, 0, j)
    if grid[m-1][j]:
        bfs(grid, visited, m-1, j)

for i in range(m):
    for j in range(n):
        if grid[i][j] and not visited[i][j]:
            grid[i][j] = 0

for i in range(m):
    for j in range(n):
        print(grid[i][j], end=" ")
        
    

103. 水流问题

  • 暴力法:直接每个位置 dfs,然后根据其最终是否能到达边界位置,返回布尔值
  • 优化思路:从边界出发,逆流而上,最终不能被访问到的地方为结果
# def dfs(grid, visited, x, y):
#     dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
#     m, n = len(grid), len(grid[0])
#     visited[x][y] = True
    
#     for add_x, add_y in dirs:
#         next_x, next_y = x + add_x, y + add_y
#         if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
#             continue
#         if grid[x][y] < grid[next_x][next_y]:
#             continue
#         if not visited[next_x][next_y]:
#             dfs(grid, visited, next_x, next_y)

# def isResult(grid, x, y):
#     m, n = len(grid), len(grid[0])
#     visited = [[False] * n for _ in range(m)]
#     dfs(grid, visited, x, y)
#     first_result, second_result = False, False
    
#     for i in range(m):
#         if visited[i][0]:
#             first_result = True
#         if visited[i][n-1]:
#             second_result = True
    
#     for j in range(n):
#         if visited[0][j]:
#             first_result = True
#         if visited[m-1][j]:
#             second_result = True
    
#     return first_result and second_result

# tmp = list(map(int, input().split()))
# m, n = tmp[0], tmp[1]

# grid = [[0] * n for _ in range(m)]
# for i in range(m):
#     tmp = list(map(int, input().split()))
#     for j in range(n):
#         grid[i][j] = tmp[j]


# for i in range(m):
#     for j in range(n):
#         if isResult(grid, i, j):
#             print("{} {}".format(i, j))

def dfs(grid, visited, x, y):
    dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    m, n = len(grid), len(grid[0])
    visited[x][y] = True
    
    for add_x, add_y in dirs:
        next_x, next_y = x + add_x, y + add_y
        if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
            continue
        # 等于不行
        if grid[x][y] > grid[next_x][next_y]:
            continue
        if not visited[next_x][next_y]:
            dfs(grid, visited, next_x, next_y)

tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]

grid = [[0] * n for _ in range(m)]
for i in range(m):
    tmp = list(map(int, input().split()))
    for j in range(n):
        grid[i][j] = tmp[j]   

visited_first = [[False]*n for _ in range(m)]
visited_second = [[False]*n for _ in range(m)]

for i in range(m):
    dfs(grid, visited_first, i, 0)
    dfs(grid, visited_second, i, n-1)

for j in range(n):
    dfs(grid, visited_first, 0, j)
    dfs(grid, visited_second, m-1, j)


for i in range(m):
    for j in range(n):
        if visited_first[i][j] and visited_second[i][j]:
            print("{} {}".format(i, j))
            

104. 建造最大岛屿

  • 暴力法:直接每个为0的位置,dfs,记录其面积
  • 优化思路:先记录每个岛屿的面积,并编号,然后 每个为0的位置,假设其为1,然后加上周围能访问到岛屿面积
    • 注意周围访问岛屿的去重问题,以及为grid 0的情况
def dfs(grid, mask, x, y, count):
    dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    m, n = len(grid), len(grid[0])
    grid[x][y] = mask
    count[0] += 1
    
    for add_x, add_y in dirs:
        next_x, next_y = x + add_x, y + add_y
        if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
            continue
        if grid[next_x][next_y] != 1 :
            continue
        dfs(grid, mask, next_x, next_y, count)


    
def main():
    tmp = list(map(int, input().split()))
    m, n = tmp[0], tmp[1]

    grid = [[0] * n for _ in range(m)]
    for i in range(m):
        tmp = list(map(int, input().split()))
        for j in range(n):
            grid[i][j] = tmp[j]   

    mask = 2
    isAllgrid = True
    gridNum = {}
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                isAllgrid = False
            if grid[i][j] == 1:
                count = [0]
                dfs(grid, mask, i, j, count)
                gridNum[mask] = count[0]
                mask += 1
            
    if isAllgrid:
        print(m*n)
        return 
    
    result = 0
    dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                tmp = 1
                visitedGrid = []
                for add_x, add_y in dirs:
                    next_x, next_y = i + add_x, j + add_y
                    if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
                        continue
                    if grid[next_x][next_y] not in visitedGrid and grid[next_x][next_y] != 0:
                        tmp += gridNum[grid[next_x][next_y]]
                        visitedGrid.append(grid[next_x][next_y])
                result = max(result, tmp)
                
    print(result)   

main()

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

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

相关文章

Android高级面试_8_热修补插件化等

Android 高级面试&#xff1a;插件化和热修复相关 1、dex 和 class 文件结构 class 是 JVM 可以执行的文件类型&#xff0c;由 javac 编译生成&#xff1b;dex 是 DVM 执行的文件类型&#xff0c;由 dx 编译生成。 class 文件结构的特点&#xff1a; 是一种 8 位二进制字节…

Linux指定文件权限的两种方式-符号与八进制数方式示例

一、指定文件权限可用的两种方式&#xff1a; 对于八进制数指定的方式&#xff0c;文件权限字符代表的有效位设为‘1’&#xff0c;即“rw-”、“rw-”、“r--”&#xff0c;以二进制表示为“110”、“110”、“100”&#xff0c;再转换为八进制6、6、4&#xff0c;所以777代表…

Log4j日志框架讲解(全面,详细)

Log4j概述 Log4j是Apache下的一款开源的日志框架&#xff0c;通过在项目中使用 Log4J&#xff0c;我们可以控制日志信息输出到控制台、文件、甚至是数据库中。我们可以控制每一条日志的输出格式&#xff0c;通过定义日志的输出级别&#xff0c;可以 更灵活的控制日志的输出过程…

pycharm中新建的临时python文件存放在哪里?

在pycharm中建立的临时python文件&#xff0c;从哪里可以找到呢&#xff1f; 1.我们打开cmd窗口&#xff0c;进入根目录&#xff0c;用dos命令“dir scratch*.py/a/s”进行查找&#xff0c;发现这些临时文件存放在Roaming\JetBrains\PyCharmCE2022.2\scratches 的目录里面 2.…

【SkiaSharp绘图14】SKCanvas方法详解(三)URL注释、按顶点绘制、 是否裁切区域之外、旋转、缩放、倾斜、平移、保存/恢复画布

文章目录 SKCanvas方法DrawUrlAnnotation 绘制URL注释DrawVertices 按顶点绘制Flush 立即绘制QuickReject 判断区域是否在裁切区域之外ResetMatrix重置矩阵Restore、RestoreToCountRotateDegrees按角度旋转画布RotateRadians按弧度旋转画布SaveLayer保存并新建图层Scale 缩放画…

海南云亿商务咨询有限公司抖店开店服务怎么样?

在数字化浪潮汹涌的当下&#xff0c;电商行业正以前所未有的速度发展&#xff0c;而抖音电商作为其中的佼佼者&#xff0c;更是吸引了无数企业和创业者的目光。海南云亿商务咨询有限公司&#xff0c;作为抖音电商服务的佼佼者&#xff0c;凭借专业的团队和丰富的经验&#xff0…

浙江建筑安全员A证2024年最新考试题库练习

46.总承包单位依法将建设工程分包给其他单位的&#xff0c;分包合同中应当明确各自的安全生产方面的权利、义务。总承包单位对分包工程的安全生产承担&#xff08;&#xff09;责任。 A.全部 B.主要 C.部分 D.连带 答案&#xff1a;D 47.实施总承报的建设工程发生事故&…

百事可乐推出具有视频屏幕和人工智能技术的智能罐头

在最近于法国戛纳举行的国际创意节上&#xff0c;百事公司推出了创新的智能罐头。这些罐头不同于传统产品&#xff0c;它们采用了环绕式3D屏幕&#xff0c;能够展示高清视频内容&#xff0c;为品牌宣传和促销带来了全新的视角。经过两年多的精心研发&#xff0c;这些智能罐成为…

github仓库的基本使用-创建、上传文件、删除

1.第一步 先点击左侧菜单栏的远程仓库 2.点击NEW 3.创建仓库 然后点击右下角的 CREATE 4.点击code 点击SSH,然后我出现了You don’t have any public SSH keys in your GitHub account. You can add a new public key, or try cloning this repository via HTTPS. 1&#xff…

《大海》这歌为何经久不衰?你看歌词写的多美妙!

《大海》这歌为何经久不衰&#xff1f;你看歌词写的多美妙&#xff01; 《大海》是一首由陈大力作词&#xff0c;陈大力、陈秀男作曲&#xff0c;Ricky Ho编曲&#xff0c;张雨生演唱的国语流行歌曲。该曲收录在张雨生1992年11月30日由飞碟唱片发行的同名专辑《大海》中。 作为…

Python特征工程 — 1.2 特征分箱

目录 1 什么是特征分箱 2 分箱的重要性及其优势 3 有监督分箱 3.1卡方分箱原理 3.2 决策树分箱 4 无监督分箱 4.1 等距分箱 4.2 等频分箱 4.3 分位数分箱 实验数据&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1yT1ct_ZM5uFLgcYsaBxnHg?pwdczum 提取码&…

CM-UNet: Hybrid CNN-Mamba UNet for Remote Sensing Image Semantic Segmentation

论文&#xff1a;CM-UNet: Hybrid &#xff1a;CNN-Mamba UNet for Remote Sensing Image Semantic Segmentation 代码&#xff1a;https://github.com/XiaoBuL/CM-UNet Abstrcat: 由于大规模图像尺寸和对象变化&#xff0c;当前基于 CNN 和 Transformer 的遥感图像语义分割方…

TongRDS2214手动部署版指引(by lqw+sy)

文章目录 前言准备工作单机版集群版哨兵版多个中心节点配置 前言 由于一些特殊原因&#xff08;例如服务器没有联网&#xff0c;没有办法直接更新和下载unzip指令&#xff0c;从而导致控制台版本安装节点之后&#xff0c;会报file not found的错误&#xff0c;或者使用不了rds…

【Flutter】列表流畅性优化

前言 在日常APP的开发中&#xff0c;列表是使用频率最高的&#xff0c;这里讲述在Flutter中优化列表的滑动速度与流畅度&#xff0c;以来提高用户的体验。 方案 1、使用ListView.builder代替ListView ListView.builder在创建列表的时候要比ListView更高效&#xff0c;因为L…

Pyramid 中混合认证策略

1. 问题背景 在一个使用 Pyramid 框架开发的应用程序中&#xff0c;需要同时处理 HTML 内容的显示和 JSON API 的请求。对于 HTML 内容&#xff0c;使用了 AuthTktAuthenticationPolicy 进行身份验证和 ACLAuthorizationPolicy 进行授权。当用户成功登录后&#xff0c;会在浏览…

sql拉链表

1、定义&#xff1a;维护历史状态以及最新数据的一种表 2、使用场景 1、有一些表的数据量很大&#xff0c;比如一张用户表&#xff0c;大约1亿条记录&#xff0c;50个字段&#xff0c;这种表 2.表中的部分字段会被update更新操作&#xff0c;如用户联系方式&#xff0c;产品的…

【哈尔滨二级等保测评需要测哪些指标】

为了保证系统的安全性、稳定性和遵从性&#xff0c;哈尔滨二级等保评估要求对评估指标进行全面的评估。下面就是对哈尔滨等保二级考核所需要的考核指标的具体说明&#xff0c;并按各个维度分点表达与总结&#xff1a; 一、物理安全要求 物理安全是信息系统的根本&#xff0c;…

kubeadm kubectl kubelet区别

kubeadm kubeadm 是一个方便易用的 Kubernetes 工具&#xff0c;能够部署生产级别的 Kubernetes 集群kubeadm 还具有了和 minikube 一样的易用性&#xff0c;只要很少的几条命令&#xff0c;如 init、join、upgrade、reset 就能够完成 Kubernetes 集群的管理维护工作&#xff…

简述设计模式-工厂模式

概述 工厂模式是为了提供创建对象的方式&#xff0c;无需制定要创建的具体类。 举个例子&#xff0c;假如我是甲方需要制造一辆车&#xff0c;我可以要油车&#xff0c;可以要电车&#xff0c;也可以油电混动车&#xff0c;如果没有工厂&#xff0c;我需要自己找到对应的制造…

免费可视化工具如何提升智慧物流管理效率

在现代智慧物流中&#xff0c;免费可视化工具正扮演着越来越重要的角色。这些工具通过数据的可视化展示&#xff0c;使物流管理更加高效、透明和智能化。免费可视化工具可以将复杂的物流数据转换为直观的图表和图形&#xff0c;帮助管理者实时监控和分析物流运作情况&#xff0…