十一、图及算法-上
本系列博客基于“ (北京大学)数据结构与算法python版”慕课,课程在中国大学慕课和bilibili上均可找到。
1. 内容
- 图数据类型的实现
- 图的应用:词梯问题
- 广度优先搜索BFS算法及其应用(骑士周游问题)
2. 课程代码
在GitHub中下载
3. OJ作业
所有代码均可在github中下载
3.1 找到小镇的法官
题目内容:
在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。如果小镇的法官真的存在,那么:
小镇的法官不相信任何人。
每个人(除了小镇法官外)都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。
给定列表 trust,该列表由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1。
输入格式: 输入包含两行,第一行为一个正整数N,第二行为信任对列表trust,以合法的Python表达式给出
输出格式: 一个整数,表示法官的编号
输入样例:
4
[[1,3],[1,4],[2,3],[2,4],[4,3]]
输出样例:
3
方法:不用建图,直接遍历 首先建立小镇人列表[1,2,3,4],然后去掉trust列表里面第一列出现的编号。对剩下的编号进行遍历,如果剩下人的编号的边有3条,则是法官 如果没有人的边是三条,则说明无法官。注意特殊情况:N=1并且信任列表为空,法官就是1号
def findJudge(N, trust):
people_list = list(range(1, N+1)) # 建立小镇人表
judge_index = -1 # 法官编号
for i in range(len(trust)): # 按行遍历
if trust[i][0] in people_list:
people_list.remove(trust[i][0]) # 去除信任别人的人
trusted_list = [b[1] for b in trust] # 被信任人列表
for j in range(len(people_list)):
if people_list[j] in trusted_list: # 如果此人有人信任
trust_num = trusted_list.count(people_list[j]) # 数有多少人信任
if trust_num == N-1: # 其他所有人都信任,说明是法官
judge_index = people_list[j]
if N == 1 and len(trust) == 0:
judge_index = 1
return judge_index
N = int(input())
trust = eval(input())
print(findJudge(N, trust))
3.2 远离大陆
题目内容:
你现在手里有一份大小为 M x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。对于每个海洋方格,其存在一个距离它最近的陆地方格,相应有一个到陆地的最小距离。请输出上述所有最小距离中的最大值。
我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果地图上只有陆地或者海洋,请返回 -1。
输入格式:
输入共1行,为一个仅包含0与1的嵌套列表,用合法的Python表达式给出
输出格式:
一个整数,表示最短距离
输入样例:
[[1,0,1],[0,0,0],[1,0,1]]
输出样例:
2
方法:广度优先搜索。把每个点的距离都算好,先把陆地设为距离0,然后搜索附近的点。因为是队列存储要搜索的点,先入先出,所以是逐渐从陆地最近的地方向远的地方搜索,所以每一步找到的海洋 都是得到的最小距离。最后从这些最短距离中找到最大的
代码
def maxDistance(grid):
# 分离陆地和海洋
ocean_list = []
land_list = []
M = len(grid) # 列
N = len(grid[0]) # 行
for i in range(len(grid)): # 行遍历
for j in range(len(grid[0])): # 列遍历
if grid[i][j] == 0: # 海洋
ocean_list.append([i, j])
else: # 陆地
land_list.append([i, j])
if len(ocean_list) == 0 or len(land_list) == 0:
return -1
max_dist = 0
for ocean in ocean_list:
each_min_dist = M+N # 最大距离
for land in land_list:
dist = abs(ocean[0]-land[0])+abs(ocean[1]-land[1])
if dist < each_min_dist:
each_min_dist = dist # 更新dist 找到对每片海洋最小的
if each_min_dist > max_dist:
max_dist = each_min_dist # 更显max_dist 找到所有海洋最大的
return max_dist
grid = eval(input())
print(maxDistance(grid))
3.3 钥匙和房间
题目内容:
有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初,除 0 号房间外的其余所有房间都被锁住。你可以*地在房间之间来回走动。请判断是否可以最终打开所有房间。
输入格式:一行嵌套列表,列表长度为N,以合法的Python表达式格式给出
输出格式:True或False,代表是否可以进入每个房间
输入样例:
[[1],[2],[3],[]]
输出样例:
True
方法:一个搜索队列,储存可以搜索的房间。一个列表存储每个房间的状态 1是已经到达,0是未到达。使用广度优先搜索
代码:
def canVisitAll(rooms):
N = len(rooms) # 房间数量
search_q = [] # 存储可以搜索的房间
room_state = [0]*N # 存储房间状态 不能搜索
room_state[0] = 1 # 准备搜索
search_q.append(0)
while search_q: # 当还有可以搜索的房间
current_room = search_q.pop(0) # 当前搜索房间
key_list = rooms[current_room] # 拿到当前房间的钥匙列表
for key in key_list:
if room_state[key] == 0: # 如果钥匙的房间没有搜索过
room_state[key] = -1 # 准备搜索
search_q.append(key) # 加入可以搜索队列
room_state[current_room] = 1 # 搜索完毕
# 搜索完毕的点 状态为1
num_searched = room_state.count(1)
if N == num_searched:
return True
else:
return False
rooms = eval(input())
print(canVisitAll(rooms))