OD 算法题 B卷【寻找最大价值的矿堆】

寻找最大价值的矿堆

• 给定一个由0、1、2组成的地图，矿堆只能由上下左右相邻的金矿、银矿连接形成，超出地图范围可以认为是空地；
• 0表示空地，1表示银矿，2表示金矿；编号表示价值；
• 找出地图中最大价值的矿堆并输出其价值；

输入描述：
地图元素
输出描述：
矿堆的最大价值

示例1
输入：
22220
00000
00000
01111
输出：
8

示例2
输入：
22220
00020
00010
01111
输出：
15

示例3
输入：
20000
00920
00000
00111
输出：
3

python实现:

• 遍历每个位置，值为1或者2时，开始以该位置为起点的广度优先搜索；
• 每次BFS都计算一次累加的价值；
• 多次BFS取最大的价值;
• 注意：不确定输入多少行时，做EOFError异常捕获；

def BFS(row, col, mat):# 存储已访问visited = []# BFS借助队列q = [(row, col)]# 四个方向directions = [0, 1, 0, -1, 0]cur_cost = 0global r, cwhile q:pos = q.pop(0)visited.append(pos)cur_row, cur_col = pos# 加当前位置的价值cur_cost += mat[cur_row][cur_col]# 搜索四个方向for d in range(4):next_row = cur_row + directions[d]next_col = cur_col + directions[d+1]# 位置有效，且为1或2 则入队if next_row >= 0 and next_row < r and next_col >= 0 and next_col < c \and mat[next_row][next_col] in [1, 2] and (next_row, next_col) not in visited:q.append((next_row, next_col))return cur_costmatrix = []
for i in range(4):  # 不确定是几行 （这里只是模拟）matrix.append([int(j) for j in input().strip()])max_cost = 0
# 获取行列数
r, c = len(matrix), len(matrix[0])
# 从1/2位置开始广度优先搜索
for r_ in range(r):for c_ in range(c):if matrix[r_][c_] in [1, 2]:cur_cost = BFS(r_, c_, matrix)if cur_cost > max_cost:max_cost = cur_cost# 输出最大价值
print(max_cost)