【代码随想录——图论——岛屿问题】

1.岛屿数量

https://kamacoder.com/problempage.php?pid=1171
在这里插入图片描述

1.1 深度优先搜索

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				dfs(i, j, &sea, &visited)
				//bfs(i, j, &sea, &visited)
				result += 1
			}
		}
	}

	fmt.Println(result)
}

func dfs(x, y int, sea *[][]int, visited *[][]bool) {
	for i := 0; i < 4; i++ {
		newX := x + direction[i][0]
		newY := y + direction[i][1]
		if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
			continue
		}
		if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
			(*visited)[newX][newY] = true
			dfs(newX, newY, sea, visited)
		}
	}
}

1.2 广度优先搜索

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				bfs(i, j, &sea, &visited)
				result += 1
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
	}
}

2.岛屿的最大面积

在这里插入图片描述

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	// 开始遍历sea
	result := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				area := bfs(i, j, &sea, &visited)
				if area>result{
				    result = area
				}
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) int {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	area := 0
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
		area += 1
	}
	return area
}

3.孤岛的总面积

在这里插入图片描述
思路：很简单，只需要优先遍历一下四周的所有点即可。

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
	var M, N int
	fmt.Scanln(&N, &M)
	sea := make([][]int, N)
	visited := make([][]bool, N)
	for i := 0; i < N; i++ {
		sea[i] = make([]int, M)
		visited[i] = make([]bool, M)
	}

	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			fmt.Scan(&sea[i][j])
		}
	}
	//优先遍历陆地边缘
	for i := 0; i < N; i++ {
		if sea[i][0] == 1 && !visited[i][0] {
			bfs(i, 0, &sea, &visited)
		}
	}
	for i := 0; i < N; i++ {
		if sea[i][N-1] == 1 && !visited[i][N-1] {
			bfs(i, N-1, &sea, &visited)
		}
	}
	
	for i := 0; i < M; i++ {
		if sea[0][i] == 1 && !visited[0][i] {
			bfs(0, i, &sea, &visited)
		}
	}
	for i := 0; i < M; i++ {
		if sea[N-1][i] == 1 && !visited[N-1][i] {
			bfs(N-1, i, &sea, &visited)
		}
	}
	// 开始遍历sea
	result := 0
	for i := 1; i < N-1; i++ {
		for j := 1; j < M-1; j++ {
			if sea[i][j] == 1 && !visited[i][j] {
				area := bfs(i, j, &sea, &visited)
				result += area
			}
		}
	}

	fmt.Println(result)
}

func bfs(i, j int, sea *[][]int, visited *[][]bool) int {
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{i, j})
	(*visited)[i][j] = true
	area := 0
	for len(queue) != 0 {
		pos := queue[0]
		for i := 0; i < 4; i++ {
			newX := pos[0] + direction[i][0]
			newY := pos[1] + direction[i][1]
			if newX < 0 || newX >= len(*sea) || newY < 0 || newY >= len((*sea)[0]) {
				continue
			}
			if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
				queue = append(queue, [2]int{newX, newY})
				(*visited)[newX][newY] = true
			}
		}
		queue = queue[1:]
		area += 1
	}
	return area
}

4.沉没孤岛

在这里插入图片描述
思路：遍历完四周之后输出visited数组即可。

package main

import "fmt"

var direction = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func main() {
    var M, N int
    fmt.Scanln(&N, &M)
    sea := make([][]int, N)
    visited := make([][]bool, N)
    for i := 0; i < N; i++ {
        sea[i] = make([]int, M)
        visited[i] = make([]bool, M)
    }

    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            fmt.Scan(&sea[i][j])
        }
    }
    
    // 优先遍历陆地边缘
    for i := 0; i < N; i++ {
        if sea[i][0] == 1 && !visited[i][0] {
            bfs(i, 0, N, M, &sea, &visited)
        }
        if sea[i][M-1] == 1 && !visited[i][M-1] {
            bfs(i, M-1, N, M, &sea, &visited)
        }
    }
    
    for i := 0; i < M; i++ {
        if sea[0][i] == 1 && !visited[0][i] {
            bfs(0, i, N, M, &sea, &visited)
        }
        if sea[N-1][i] == 1 && !visited[N-1][i] {
            bfs(N-1, i, N, M, &sea, &visited)
        }
    }
    
    // 开始遍历visited
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            if visited[i][j] {
                fmt.Print(1)
            } else {
                fmt.Print(0)
            }
            fmt.Print(" ")
        }
        fmt.Println()
    }
}

func bfs(i, j, N, M int, sea *[][]int, visited *[][]bool) int {
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{i, j})
    (*visited)[i][j] = true
    area := 0
    for len(queue) != 0 {
        pos := queue[0]
        queue = queue[1:]
        area += 1
        for i := 0; i < 4; i++ {
            newX := pos[0] + direction[i][0]
            newY := pos[1] + direction[i][1]
            if newX < 0 || newX >= N || newY < 0 || newY >= M {
                continue
            }
            if (*sea)[newX][newY] == 1 && !(*visited)[newX][newY] {
                queue = append(queue, [2]int{newX, newY})
                (*visited)[newX][newY] = true
            }
        }
    }
    return area
}

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

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

相关文章

SSRS中生成二维码

SSRS中生成二维码

1.二维码搭建, fastapi,qrcode,python-barcode from fastapi import FastAPI, HTTPException from pydantic import BaseModel import qrcode from io import BytesIO from fastapi.responses import StreamingResponse import barcode from barcode.writer import ImageWrite…
阅读更多...
关于Unity粒子（2D序列帧粒子）的旋转、StartRotation值用脚本怎么动态设置

关于Unity粒子（2D序列帧粒子）的旋转、StartRotation值用脚本怎么动态设置

今天要用粒子做一个拖尾效果。由于对象的移动可以向任何方向&#xff0c;所以作为拖尾的粒子要根据方向做相应的旋转。 1.没有旋转的情况&#xff08;物体向下移动&#xff09;时&#xff0c;默认是下面这样的。 粒子发射器的形状是一个向上的长方形&#xff0c;粒子的移动方向…
阅读更多...
在Linux系统中配置GitHub的SSH公钥

在Linux系统中配置GitHub的SSH公钥

在Linux系统中配置GitHub的SSH公钥&#xff0c;可以让您无需频繁输入密码即可与GitHub仓库进行交互&#xff0c;提高工作效率。以下是配置步骤: 第一步&#xff1a; 检查SSH密钥是否存在 首先&#xff0c;检查您的用户目录下的.ssh文件夹中是否已有SSH密钥。打开终端&#xff0…
阅读更多...
Interview preparation--Https 工作流程

Interview preparation--Https 工作流程

HTTP 传输的弊端 如上图&#xff0c;Http进行数据传输的时候是明文传输&#xff0c;导致任何人都有可能截获信息&#xff0c;篡改信息如果此时黑客冒充服务器&#xff0c;或者黑客窃取信息&#xff0c;则其可以返回任意信息给客户端&#xff0c;而且不被客户端察觉&#xff0c;…
阅读更多...
Java经典面试题将一个字符串数组进行分组输出，每组中的字符串都由相同的字符组成

Java经典面试题将一个字符串数组进行分组输出，每组中的字符串都由相同的字符组成

Java经典面试题将一个字符串数组进行分组输出&#xff0c;每组中的字符串都由相同的字符组成 题目&#xff1a; 将一个字符串数组进行分组输出&#xff0c;每组中的字符串都由相同的字符组成 举个例子&#xff1a;输入[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”] 输出…
阅读更多...
考CFA ESG踩过的坑，想考CFA ESG的同学，可以收藏

考CFA ESG踩过的坑，想考CFA ESG的同学，可以收藏

考CFA ESG踩过的坑 考证也是蹭热点&#xff0c; 2020年&#xff0c;那时是云&#xff0c;阿里云&#xff0c;腾讯云&#xff0c;华为云竞相绽放&#xff0c; 再过点时间&#xff0c;好像安全方面的证书&#xff0c;如油炸爆米花一样&#xff0c;噼里啪啦地蹦了出来&#xff0…
阅读更多...
基于STM32与ESP8266的智能电表设计与实现：实时监测，远程管理（附代码实例）

基于STM32与ESP8266的智能电表设计与实现：实时监测，远程管理（附代码实例）

一、项目背景 随着物联网技术的快速发展&#xff0c;传统电表已经无法满足智能电网对用电信息采集、分析和管理的需求。智能电表作为新一代电能计量设备&#xff0c;具有实时监测、远程抄表、用电分析等功能&#xff0c;是实现智能电网的重要基础设施。 本项目旨在设计并实现…
阅读更多...
猫狗图像分类-划分数据集

猫狗图像分类-划分数据集

&#x1f4da;博客主页&#xff1a;knighthood2001 ✨公众号&#xff1a;认知up吧 &#xff08;目前正在带领大家一起提升认知&#xff0c;感兴趣可以来围观一下&#xff09; &#x1f383;知识星球&#xff1a;【认知up吧|成长|副业】介绍 ❤️如遇文章付费&#xff0c;可先看…
阅读更多...
【Linux】：程序地址空间

【Linux】：程序地址空间

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux程序地址空间的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从…
阅读更多...
css使用伪元素after或者before的时候想要给after设置z-index无效

css使用伪元素after或者before的时候想要给after设置z-index无效

css使用伪元素after或者before的时候想要给after或者before设置一个层级关系&#xff0c;使该伪类写入的样式在box的下面&#xff0c;发现给box设置z-index无效&#xff0c; 需要找到父级元素&#xff0c;在父级元素上设置z-index值并且将伪类设置z-index:-1
阅读更多...
【Whisper】WhisperX: Time-Accurate Speech Transcription of Long-Form Audio

【Whisper】WhisperX: Time-Accurate Speech Transcription of Long-Form Audio

Abstract Whisper 的跨语言语音识别取得了很好的结果&#xff0c;但是对应的时间戳往往不准确&#xff0c;而且单词级别的时间戳也不能做到开箱即用(out-of-the-box). 此外&#xff0c;他们在处理长音频时通过缓冲转录
阅读更多...
Spark快速大数据分析PDF下载读书分享推荐

Spark快速大数据分析PDF下载读书分享推荐

《Spark 快速大数据分析》是一本为 Spark 初学者准备的书&#xff0c;它没有过多深入实现细节&#xff0c;而是更多关注上层用户的具体用法。不过&#xff0c;本书绝不仅仅限于 Spark 的用法&#xff0c;它对 Spark 的核心概念和基本原理也有较为全面的介绍&#xff0c;让读者能…
阅读更多...
Elasticsearch：Runtime fields - 运行时字段（一）

Elasticsearch：Runtime fields - 运行时字段（一）

目录 使用运行时字段带来的好处 激励 折衷 映射运行时字段 定义运行时字段而不使用脚本 忽略运行时字段上的脚本错误 更新和删除运行时字段 在搜索请求中定义运行时字段 创建使用其他运行时字段的运行时字段 运行时字段&#xff08;runtime fields&#xff09;是在查询…
阅读更多...
golang结合neo4j实现权限功能设计

golang结合neo4j实现权限功能设计

neo4j 是非关系型数据库之图形数据库&#xff0c;这里不再赘述。 传统关系数据库基于rbac实现权限, user ---- role ------permission,加上中间表共5张表。 如果再添上部门的概念&#xff1a;用户属于部门&#xff0c;部门拥有 角色&#xff0c;则又多了一层&#xff1a; user-…
阅读更多...
WPF UI 界面布局 魔术棒 文字笔记识别 技能提升 布局功能扩展与自定义 继承Panel的对象，测量与排列 系列七

WPF UI 界面布局 魔术棒 文字笔记识别 技能提升 布局功能扩展与自定义 继承Panel的对象，测量与排列 系列七

应用开发第一步 功能分类&#xff1a;页面上的功能区域划分。。。。需求分析 业务逻辑 数据流 功能模块 UI/UX 编码 测试 发布 功能开发与布局 不用显式的方式设定元素的尺寸 不使用屏幕坐标来指定位置 Grid 功能最强大&#xff0c;布局最灵活的容器…
阅读更多...
代码提交错分支了怎么办？

代码提交错分支了怎么办？

你有么有遇到过正在开发的代码&#xff0c;提交到生产环境的分支去&#xff0c;遇到这种情况怎么办&#xff1f; 问题重现&#xff1a; 这段注释// AAAAAAAAAAA 本来应该写在dev分支的&#xff0c;现在提交并push到master分支了 现在第一步&#xff0c;撤回提交 第二步&…
阅读更多...
第五届机械工程与智能制造国际学术会议(MEIM 2024，7月26-28)

第五届机械工程与智能制造国际学术会议(MEIM 2024，7月26-28)

第五届机械工程与智能制造国际学术会议(MEIM 2024) 计划2024年7月26-28日在中国辽宁锦州隆重举行。本次会议由辽宁理工学院主办。 会议主要围绕机械工程与智能制造等研究领域展开讨论&#xff0c;旨在为从事机械工程与智能制造研究的专家学者、程技术人员、技术研发人员提供一个…
阅读更多...
Midjourney 如何使用参考图像来提升图像的准确性和相似度？

Midjourney 如何使用参考图像来提升图像的准确性和相似度？

🧙🏼图像提示 🧙🏼‍♂️ 您可以使用图像作为提示的一部分来影响作业的构图、样式和颜色。图像提示可以单独使用，也可以与文本提示一起使用 - 尝试组合具有不同样式的图像以获得最令人兴奋的结果。 🛠️实际图像提示操作步骤 点击加号按钮，双击上传文件，把小黄猫…
阅读更多...
SwiftUI 6.0（iOS 18.0）滚动视图新增的滚动阶段（Scroll Phase）监听功能趣谈

SwiftUI 6.0（iOS 18.0）滚动视图新增的滚动阶段（Scroll Phase）监听功能趣谈

何曾几时&#xff0c;在 SwiftUI 开发中的秃头小码农们迫切需要一种能够读取当前滚动状态的方法。 在过去&#xff0c;他们往往需要借助于 UIKit 的神秘力量。不过这一切在 SwiftUI 6.0 中已成“沧海桑田”。 在本篇博文中&#xff0c;您将学到如下内容&#xff1a; 1. Scroll…
阅读更多...
Anubi WebKey开启去中心化数字革命的新纪元

Anubi WebKey开启去中心化数字革命的新纪元

随着技术的飞速发展&#xff0c;Web3正在重新定义未来互联网的架构&#xff0c;标志着从集中式控制向去中心化自主的历史性转变。在这场全球性的技术演变中&#xff0c;Anubi WebKey不仅仅是一款前沿的智能设备&#xff0c;它代表的是一种划时代的技术革命&#xff0c;一个重塑…
阅读更多...
最新文章

Copyright @ 2022~2023