首页 > 编程语言 >代码随想录算法训练营第53天 | 图论2：岛屿数量相关问题

代码随想录算法训练营第53天 | 图论2：岛屿数量相关问题

时间：2024-07-31 11:42:11浏览次数：15  
标签：count 图论 graph 随想录 53 range visited nextx nexty

99.岛屿数量
https://kamacoder.com/problempage.php?pid=1171
岛屿深搜
https://www.programmercarl.com/kamacoder/0099.岛屿的数量深搜.html
岛屿广搜
https://www.programmercarl.com/kamacoder/0099.岛屿的数量广搜.html#思路
100.岛屿的最大面积
https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html
代码随想录
https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html

岛屿数量

岛屿深搜

  • 两种写法：可以把终止条件写在前面 也可以写在循环内；

    • 区别：把判断条件写在main函数或写在dfs函数中

  • 采用递归

    深搜方法1：停止条件在主函数中 
    def dfs(graph,visited,x,y,count):
	directions = [[0,-1],[0,1],[1,0],[-1,0]]
	for dir_ in directions:
		nextx = x+dir_[0]
		nexty = y+dir_[1]
		if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph):
			continue
		if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
			visited[nextx][nexty] = 1 ##执行访问
			dfs(graph,visited,nextx,nexty,count)
def main():
	## 初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	visited = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])
	#分别统计
	count = 0
	for i in range(n):
		for j in range(m):
			##停止条件
			if graph[i][j]==1 and visited[i][j]==0:
				count+=1
				dfs(graph,visited,i,j,count)
	print(count)
if __name__ == '__main__':
	main()
    深搜方法2：停止条件在递归函数中 
    def dfs(graph,visited,x,y):
	if visited[x][y] or graph[x][y]==0:
		return
	visited[x][y] = True
	dirs = [[0,-1],[0,1],[1,0],[-1,0]]
	for i in range(4):
		nextx = x+dirs[i][0]
		nexty = y+dirs[i][1]
		if (nextx)<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]):
			continue
		dfs(graph,visited,nextx,nexty)
def main():
	##初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])
	visited = [[False]*(m) for _ in range(n)]
	##递归计数
	count = 0
	for i in range(n):
		for  j in range(m):
			if not visited[i][j] and graph[i][j]==1:
				count+=1
				dfs(graph,visited,i,j)
	print(count)
if __name__ == '__main__':
	main()

岛屿广搜

  • 不需要递归

  • 加入队列即为访问过了

    广度搜索代码 
    def dfs(graph,visited,x,y,count):
	directions = [[0,-1],[0,1],[1,0],[-1,0]]
	queue = [[x,y]]
	while queue:
		curr = queue.pop()
		x = curr[0]
		y = curr[1]
		visited[x][y] = 1
		for dir_ in directions:
			nextx = x+dir_[0]
			nexty = y+dir_[1]
			if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph):
				continue
			if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
				visited[nextx][nexty] = 1
				dfs(graph,visited,nextx,nexty,count)

def main():
	## 初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	visited = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])

	#分别统计
	count = 0
	for i in range(n):
		for j in range(m):
			if graph[i][j]==1 and visited[i][j]==0:
				count+=1
				dfs(graph,visited,i,j,count)
	print(count)

岛屿最大面积

  • 和岛屿广搜一样的

    深度优先搜索1 
    def dfs(graph,visited,x,y):
	if graph[x][y]==0 or visited[x][y]==1:
		return 0
	count = 1
	visited[x][y] = 1
	directions = [[0,1],[0,-1],[1,0],[-1,0]]
	for dir_ in directions:
		nextx = x+dir_[0]
		nexty = y+dir_[1]
		if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph):
			continue
		if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
			count += dfs(graph,visited,nextx,nexty)
	return count
def main():
	## 初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	visited = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])
	#分别统计
	res = 0
	for i in range(n):
		for j in range(m):
			##停止条件
			if graph[i][j]==1 and visited[i][j]==0:
			 #   visited[i][j] = 1
			 #   count = 0
				count = dfs(graph,visited,i,j)
				res = max(res,count)
	print(res)

if __name__ == '__main__':
	main()
    深度优先搜索2 
    def dfs(graph,visited,x,y,count):
	directions = [[0,1],[0,-1],[1,0],[-1,0]]
	for dir_ in directions:
		nextx = x+dir_[0]
		nexty = y+dir_[1]
		if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph):
			continue
		if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
			visited[nextx][nexty] = 1 ##执行访
			count+=1
			count = dfs(graph,visited,nextx,nexty,count)
	return count

def main():
	## 初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	visited = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])
	#分别统计
	res = 0
	for i in range(n):
		for j in range(m):
			##停止条件
			if graph[i][j]==1 and visited[i][j]==0:
				visited[i][j] = 1
				count = 1
				count = dfs(graph,visited,i,j,count)
				res = max(res,count)
	print(res)

if __name__ == '__main__':
	main()
    广度优先搜索 
    def dfs(graph,visited,x,y):
	queue = [[x,y]]
	directions = [[0,1],[0,-1],[1,0],[-1,0]]
	count = 1
	visited[x][y] = 1
	while queue:
		curr = queue.pop()
		x = curr[0]
		y = curr[1]
		for dir_ in directions:
			nextx = x+dir_[0]
			nexty = y+dir_[1]
			if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph):
				continue
			if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
				visited[nextx][nexty]=1
				count+=1
				queue.append([nextx,nexty])
	return count

def main():
	## 初始化
	n,m = map(int,input().split())
	graph = [[0]*(m) for _ in range(n)]
	visited = [[0]*(m) for _ in range(n)]
	for i in range(n):
		data = input().split()
		for j in range(m):
			graph[i][j] = int(data[j])
	#分别统计
	res = 0 
	for i in range(n):
		for j in range(m):
			##停止条件
			if graph[i][j]==1 and visited[i][j]==0:
				count = dfs(graph,visited,i,j)
				res = max(res,count)
	print(res)

if __name__ == '__main__':
	main()

标签：count,图论,graph,随想录,53,range,visited,nextx,nexty
From： https://www.cnblogs.com/P201821440041/p/18332673

相关文章

  • 代码随想录 day40 打家劫舍 及其变体
    打家劫舍打家劫舍解题思路动态规划解决问题，通过前两个值决定第三个值，需要注意的是初始值的选择，第二个的值是取前两个数中较大的，这样是为了保证跳过不需要取的值知识点动态规划心得初始值的选择没有考虑到，其余的都写出来了打家劫舍二打家劫舍二解题思路前一题的改进，只......
  • 代码随想录算法训练营Day0| LeetCode704: 二分查找
    LeetCode704二分查找先看了一下数组理论基础：数组基础题目链接：704.二分查找啥也没看，凭感觉直接上手：classSolution(object): defsearch(self,nums,target): fornuminnums: ifnum==target: returnnums.index(num) break return-1通过倒是......
  • Luogu P1983 车站分级 题解 [ 绿 ] [ 拓扑排序 ] [ 图论建模 ] [ 虚点 ]
    车站分级：很好的拓扑排序题，细节有点多。图论建模首先观察对于一条线路，我们可以从中直接得到什么信息：假设这条线路的开头为\(st\)，结尾为\(ed\)，那么在\([st,ed]\)的车站中，没有被选入线路的点一定比选入线路的点的级数至少少\(1\)。对于这一点条件，我们就可以建模了。......
  • CF538H Summer Dichotomy 题解
    Description有\(T\)名学生，你要从中选出至少\(t\)人，并将选出的人分成两组，可以有某一组是空的。有\(n\)名老师，每名老师要被分配到两个小组之一，对于第\(i\)名老师，要求所在的小组中的学生人数\(\in[l_i,r_i]\)。此外，有\(m\)对老师不能在同一个小组中。你需要判断能否......
  • 代码随想录二刷(链表章节)
    代码随想录二刷(链表章节)链表就是通过指针串联在一起的线性结构，每个节点都是由一个数据域和指针域(存放下一个节点的指针)。双链表就是每个节点中既有指向前一个节点的，也有指向后一个节点的。循环链表就是把头和尾连起来。性能分析如下：下面来看下链表的具体题目：Leetcod......
  • 【笔记】图论：2-sat、连通性、欧拉回路选讲
    [AGC059C]GuessingPermutationforasLongasPossible（2-sat）这个东西十分智障，只需要对于所有\(a,b,c\)，如果询问顺序是\((a,b),(b,c),(a,c)\)，那么不能\(a<b<c\)或\(a>b>c\)。其它的情况（一条链）你一看发现肯定需要出现上述情况，那么这就是充要条件。你一看你直接对所......
  • 代码随想录day14 || 226 翻转二叉树，101 对称二叉树， 104 二叉树的最大深度， 111 二叉树
    226翻转二叉树funcinvertTree(root*TreeNode)*TreeNode{ //思考，广度优先遍历，对于每一层，翻转其左右子节点 ifroot==nil{ returnnil } queue:=list.New() queue.PushBack(root) size:=1//存储每一层的节点个数 forqueue.Len()>0{ varcountint ......
  • 代码随想录算法训练营第28天 | 贪心进阶
    2024年7月30日题122.买卖股票的最佳时机II上涨就买，下跌就不买。classSolution{publicintmaxProfit(int[]prices){intsum=0;for(inti=1;i<prices.length;i++){sum+=prices[i]-prices[i-1]>0?prices[i]-prices[i-1]:0;......
  • 代码随想录算法训练营第27天 | 初入贪心
    2024年7月29日题455.分发饼干先排序，然后依次分发即可。classSolution{publicintfindContentChildren(int[]g,int[]s){//对于每个孩子胃口，从小到大分配，且给尽可能少的饼干Arrays.sort(g);Arrays.sort(s);intcnt=0;......
  • 温度补偿 MEMS 振荡器（TC-MO/VC TC-MO） - Super Low Jitter MO5155/MO5156/MO5157/MO535
    在当今科技高速发展的时代，电子设备对频率源的性能要求日益严苛。频率的稳定性、精度以及低抖动特性成为了决定设备性能的关键因素。温度补偿MEMS振荡器（TC-MO/VCTC-MO）以其出色的性能，正在逐渐成为电子领域的宠儿。本文将详细介绍SuperLowJitter系列的MO5155、MO5156、......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99