算法训练营day53 图论④ 110.字符串接龙、105.有向图的完全可达性、106.岛屿的周长
图论，继续加深基础的掌握，进入图论以来，感觉代码难度瞬间上升了，ACM模式还是有难度的
110.字符串接龙
这道题的图结构相对困难一些，没有之前用矩阵来的直观，所以首先要构建图（代码中没有明显构建，仅做了数组中的遍历，所以广度搜索的思想是很宽泛的，要学会变通），然后使用广度搜索查找最近路径
map函数和循环输入要掌握
def judge(s1,s2):count=0for i in range(len(s1)):if s1[i]!=s2[i]:count+=1return count==1if __name__=='__main__':n=int(input())beginstr,endstr=map(str,input().split())if beginstr==endstr:print(0)exit()strlist=[]for i in range(n):strlist.append(input())# use bfsvisit=[False for i in range(n)]queue=[[beginstr,1]]while queue:str,step=queue.pop(0)if judge(str,endstr):print(step+1)exit() # 结束整个程序运行for i in range(n):if visit[i]==False and judge(strlist[i],str):visit[i]=Truequeue.append([strlist[i],step+1])print(0)105.有向图的完全可达性
这道题只需要查找能否到其他各个节点，类似于“蔓延”，所以使用广度搜索
其实不是很好想，所以还是需要更加牢固掌握广度搜索
import collections # 导入collections模块，用于创建队列和默认字典path = set() # 用于记录BFS遍历过程中经过的所有节点（使用集合避免重复记录）def bfs(root, graph):"""广度优先搜索(BFS)函数：从指定根节点开始遍历图参数:root: 起始遍历的根节点graph: 用字典表示的图结构，键为节点，值为该节点的邻接节点列表"""global path # 声明使用全局变量path# 创建一个双端队列，并将起始根节点加入队列（初始化队列）que = collections.deque([root])# 当队列不为空时，持续进行BFS遍历while que:# 从队列左侧取出一个节点作为当前处理节点cur = que.popleft()# 将当前节点加入已访问路径集合path.add(cur)# 遍历当前节点的所有邻接节点for nei in graph[cur]:# 将邻接节点加入队列，等待后续遍历que.append(nei)# 清空当前节点的邻接列表（避免后续重复处理该节点的邻接关系）graph[cur] = []return # 遍历完成后返回def main():"""主函数：读取输入、构建图、执行BFS并判断结果"""# 读取第一行输入，获取节点总数N和边的数量KN, K = map(int, input().strip().split())# 创建一个默认字典作为图的容器，键为节点，值为邻接节点列表（自动处理不存在的键）graph = collections.defaultdict(list)# 循环读取K条边的信息，构建图结构for _ in range(K):# 每条边包含源节点src和目标节点dest，表示从src到dest有一条有向边src, dest = map(int, input().strip().split())graph[src].append(dest) # 将目标节点添加到源节点的邻接列表中# 从节点1开始执行BFS遍历bfs(1, graph)# 判断BFS遍历过的节点是否包含了所有从1到N的节点# {i for i in range(1, N + 1)} 生成包含1到N所有整数的集合if path == {i for i in range(1, N + 1)}:return 1 # 如果所有节点都被遍历到，返回1return -1 # 否则返回-1if __name__ == "__main__":# 程序入口：执行主函数并打印返回结果print(main())补充深度搜索代码
visit数组没有回溯！
def dfs(graph, key, visited):for neighbor in graph[key]:if not visited[neighbor]: # Check if the next node is not visitedvisited[neighbor] = Truedfs(graph, neighbor, visited)def main():import sysinput = sys.stdin.readdata = input().split()n = int(data[0])m = int(data[1])graph = [[] for _ in range(n + 1)]index = 2for _ in range(m):s = int(data[index])t = int(data[index + 1])graph[s].append(t)index += 2visited = [False] * (n + 1)visited[1] = True # Process node 1 beforehanddfs(graph, 1, visited)for i in range(1, n + 1):if not visited[i]:print(-1)returnprint(1)if __name__ == "__main__":main()
106.岛屿的周长
方法一：遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。如果该陆地上下左右的空格是有水域，则说明是一条边
方法二： result = 岛屿数量 * 4 - cover * 2
所以解题要灵活，下面以方法二为例，仅使用简单for循环即可
def main():import sys# 读取所有输入数据（一次性读取提高效率）input = sys.stdin.readdata = input().split() # 将输入按空格分割成列表# 读取网格的行数n和列数m（数据的前两个元素）n = int(data[0])m = int(data[1])# 初始化网格gridgrid = []index = 2 # 从第三个元素开始是网格数据for i in range(n):# 每行取m个元素，组成一行网格数据grid.append([int(data[index + j]) for j in range(m)])index += m # 移动索引到下一行的起始位置sum_land = 0 # 统计网格中陆地（值为1）的总数量cover = 0 # 统计相邻陆地之间的接壤边数（每相邻一对陆地会共享一条边）# 遍历网格中的每个单元格for i in range(n):for j in range(m):if grid[i][j] == 1: # 如果当前单元格是陆地sum_land += 1 # 陆地数量加1# 统计与上方单元格的相邻情况（避免重复统计，只查上和左）if i - 1 >= 0 and grid[i - 1][j] == 1:cover += 1 # 上方也是陆地，接壤边数加1# 统计与左侧单元格的相邻情况if j - 1 >= 0 and grid[i][j - 1] == 1:cover += 1 # 左侧也是陆地，接壤边数加1# 注意：不统计下方和右侧的相邻情况，避免同一对陆地被重复计算# 例如：(i,j)和(i+1,j)的相邻关系，会在(i+1,j)检查上方时统计# 计算总周长：# 每个陆地初始有4条边，所有陆地总边数为 sum_land * 4# 每有一对相邻陆地，会共享一条边，每条共享边会使总周长减少2（两边各减1）result = sum_land * 4 - cover * 2print(result)if __name__ == "__main__":main()