110.字符串接龙
https://kamacoder.com/problempage.php?pid=1183
代码随想录
https://www.programmercarl.com/kamacoder/0110.字符串接龙.html#思路
105.有向图的完全可达性
https://kamacoder.com/problempage.php?pid=1177
代码随想录
https://www.programmercarl.com/kamacoder/0105.有向图的完全可达性.html
106.岛屿的周长
https://kamacoder.com/problempage.php?pid=1178
代码随想录
https://www.programmercarl.com/kamacoder/0106.岛屿的周长.html#思路
110.字符串接龙
-
step1：根据字符串建立图（邻接表）；
-
step2：无向图求最短路径：广度优先搜索；
-
广搜逻辑：
- 一定要用队列：先进先出；
点击查看代码
from collections import deque def main(): dict_num = int(input()) source,target = input().split() dict_str = [source] for i in range(dict_num): dict_str.append(input()) dict_str.append(target) path_li = {} for i in range(len(dict_str)): path_li[i] = [] for j in range(len(dict_str)): if i==j: continue if pre_distance(dict_str[i],dict_str[j])==1: path_li[i].append(j) res = bfs_path(path_li,0,dict_num+1) print(res) def bfs_path(graph,start,end): queue = deque([(start,[start])]) visited = set() while queue: node,path = queue.popleft() if node==end: return len(path) if node not in visited: visited.add(node) if len(graph[node])==0: break return 0 for neighbor in graph[node]: if neighbor not in visited: queue.append((neighbor,path+[neighbor])) return [] def pre_distance(str1,str2): distance = 0 for i in range(len(str1)): if str1[i]!=str2[i]: distance+=1 return distance if __name__ == '__main__': main()
105.有向图的完全可达性
-
两种方式进行深搜：
- 当前值执行；
当前值执行
def main(): n,k = map(int,input().split()) graph = {i:[] for i in range(n+1)} for i in range(k): s,t = map(int,input().split()) graph[s].append(t) visited = [0]*(n+1) dfs(graph,visited,1) for i in range(1,n+1): if visited[i]==0: print("-1") return print("1") def dfs(graph,visited,node): if visited[node]==1: return visited[node] =1 if len(graph[node])!=0: for key in graph[node]: dfs(graph,visited,key) if __name__ == '__main__': main()- 处理过当前值循环；（和BFS的位置相同）
处理过当前值循环
from collections import deque def main(): n,k = map(int,input().split()) graph = {i:[] for i in range(n+1)} for i in range(k): s,t = map(int,input().split()) graph[s].append(t) visited = [0]*(n+1) visited[1] = 1 bfs(graph,visited,1) for i in range(1,n+1): if visited[i]==0: print("-1") return print("1") def dfs(graph,visited,node): visited[node] =1 if len(graph[node])!=0: for key in graph[node]: if visited[key]==0: dfs(graph,visited,key) def bfs(graph,visited,node): queue = deque([node]) while queue: curr =queue.popleft() for key in graph[curr]: if visited[key]==0: visited[key]=1 queue.append(key) if __name__ == '__main__': main()
106. 岛屿的周长
-
统计岛屿的周长；
-
方法一：所有块的数量4-重合数量2
点击查看代码
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]) directions = [[0,1],[0,-1]] bound = 0 combine = 0 for i in range(n): for j in range(m): if graph[i][j]==1: bound+=1 if i-1>=0 and graph[i-1][j]==1: combine+=1 if j-1>=0 and graph[i][j-1]==1: combine+=1 print(str(bound*4-combine*2)) if __name__ == '__main__': main() -
方法二：遇到了边缘块 统计边缘数量即可
点击查看代码
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]) directions = [[0,1],[0,-1],[1,0],[-1,0]] bound = 0 for i in range(n): for j in range(m): if graph[i][j]==1: for dir_ in directions: nextx = i+dir_[0] nexty = j+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): bound+=1 elif graph[nextx][nexty]==0: bound+=1 else: continue print(bound) if __name__ == '__main__': main()