day53-graph theory-part04-8.24

1. 110.字符串接龙

the shitty configuration on kc web is disgusting

pay attention to the list form string and oure string

the path + 1 should not be directly assigned to path

from collections import deque, defaultdictdef main():n = int(input())startStr, endStr = input().split()strSet = []for i in range(n):strSet.append(input())# print(n, strSet)bfsQueue = deque()visited = defaultdict()bfsQueue.append(startStr)visited[startStr] = 1while bfsQueue:curStr = bfsQueue.popleft()path = visited[curStr]for i in range(len(curStr)):newStr = list(curStr)for j in range(26):newStr[i] = chr(ord('a')+j)# print(''.join(newStr))# print(bfsQueue)# print(visited.keys())new = ''.join(newStr)if new == endStr: print(path+1)returnif (new in strSet) and (new not in visited):visited[new] = path + 1bfsQueue.append(new)print(0)returnif __name__ == "__main__":main()

2. 105.有向图的完全可达性

this practice is suitable for using adjcent table

from collections import defaultdictdef dfs(graph, visited, key):if visited[key]:return visited[key] = Truekeys = graph[key]for i in keys:dfs(graph, visited, i)def main():n, m = map(int, input().split())graph = defaultdict(list)visited = [False] * nfor i in range(m):start, end = map(int, input().split())graph[start-1].append(end-1)# print(graph)dfs(graph, visited, 0)for i in range(n):if visited[i] == False:print(-1)returnprint(1)returnif __name__ == "__main__":main()

3. 106.岛屿的周长

pay attention to this practice, this is related to the perimeter of island, instead of the area.

It is not necessary to use BFS or DFS in this practice.

def main():n, m = map(int, input().split())graph = []for _ in range(n):graph.append(list(map(int, input().split())))total = 0cover = 0for i in range(n):for j in range(m):if graph[i][j] == 1:total += 1if i-1 >= 0 and graph[i-1][j] == 1: cover += 1if j-1 >= 0 and graph[i][j-1] == 1: cover += 1result = total * 4 - cover * 2print(result)if __name__ == "__main__":main()