代码随想录算法训练营 Day 46
Published:
Q1. KamaCoder 110
本题中要找到最短路径，因此使用广度优先搜索。当走到终点时，直接输出结果即可
from collections import deque
def check_valid_convert(s1, s2):
count = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
count += 1
return True if count == 1 else False
if __name__ == '__main__':
n = int(input())
begin_str, end_str = input().split()
str_lst = []
for _ in range(n):
str_lst.append(input())
if begin_str == end_str:
print(0)
exit()
vis = set()
queue = deque([(begin_str, 1)])
while queue:
curr_str, l = queue.popleft()
if check_valid_convert(curr_str, end_str):
print(l + 1)
exit()
for i in range(n):
if str_lst[i] not in vis and check_valid_convert(curr_str, str_lst[i]):
queue.append((str_lst[i], l + 1))
vis.add(str_lst[i])
print(0)
Q2. KamaCoder 105
从节点1开始遍历，并且用一个集合记录遍历过的节点，最后判断集合长度是否等于节点数量
深度优先遍历
from collections import defaultdict
def dfs(node):
for neigh in edge[node]:
if neigh not in vis:
vis.add(neigh)
dfs(neigh)
if __name__ == '__main__':
n, k = map(int, input().split())
edge = defaultdict(list)
for _ in range(k):
n1, n2 = map(int, input().split())
edge[n1].append(n2)
vis = {1}
dfs(1)
print(1 if len(vis) == n else -1)
from collections import defaultdict
def dfs(node):
if node in vis:
return
vis.add(node)
for neigh in edge[node]:
dfs(neigh)
if __name__ == '__main__':
n, k = map(int, input().split())
edge = defaultdict(list)
for _ in range(k):
n1, n2 = map(int, input().split())
edge[n1].append(n2)
vis = set()
dfs(1)
print(1 if len(vis) == n else -1)
广度优先搜索
from collections import defaultdict, deque
def bfs(node, vis):
queue = deque([node])
while queue:
curr_node = queue.popleft()
vis.add(curr_node)
for neigh in edge[curr_node]:
if neigh not in vis:
queue.append(neigh)
return vis
if __name__ == '__main__':
n, k = map(int, input().split())
edge = defaultdict(list)
for _ in range(k):
n1, n2 = map(int, input().split())
edge[n1].append(n2)
vis = bfs(1, set())
print(1 if len(vis) == n else -1)
Q3. KamaCoder 103
每个格子一共有四条边，分别和四个方向的邻居格子共用。如果陆地和海相邻或者陆地是边界，则周长加1；如果陆地和陆地相邻，那么它们之间公共的格子就不能算进周长中
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
for dx, dy in directions:
x, y = i + dx, j + dy
if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == 0:
res += 1
print(res)