【DFS/BFS】2023B-寻找最大价值的矿堆
题目描述与示例
给你一个由 '0'
(空地)、'1'
(银矿)、'2'
(金矿)组成的的地图,矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
假设银矿价值 1
,金矿价值 2
,请你找出地图中最大价值的矿堆并输出该矿堆的价值。
输入
地图元素信息如:
22220
00000
00000
01111
地图范围最大为 300 * 300
,0 <= 地图元素 <= 2
输出
矿堆的最大价值。
示例一
输入
22220
00000
00000
01111
输出
8
示例二
输入
22220
00020
00010
01111
输出
15
示例三
输入
20000
00020
00000
00111
输出
3
解题思路
注意,本题和LC695. 岛屿的最大面积几乎完全一致。唯一的区别在于,本题包含1
和2
两种不同价值的矿物。
代码
解法一:BFS
# 题目:2023B-寻找价值最大的矿堆
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:BFS
# 代码看不懂的地方,请直接在群上提问
from collections import deque
# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]
# 输入地图
grid = list()
while True:
row = input()
if len(row) == 0:
break
grid.append(row)
# 根据地图获得行数、列数
n, m = len(grid), len(grid[0])
# 答案变量,用于记录价值最大的矿堆
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过,1表示检查过了
check_list = [[0] * m for _ in range(n)]
# 最外层的大的双重循环,是用来找BFS的起始搜索位置的
for i in range(n):
for j in range(m):
# 找到一个"1"或"2",并且这个点从未被搜索过:那么可以进行BFS的搜索
# 1. 值是"1"或"2" 2. 没被搜索过
if grid[i][j] != "0" and check_list[i][j] == 0:
# BFS的过程
q = deque()
q.append([i, j]) # BFS的起始点
check_list[i][j] = 1
cur_value = 0 # 初始化当前矿堆的价值为0
while len(q) > 0: # 当队列中还有元素时,持续地进行搜索
qSize = len(q)
for _ in range(qSize):
# 弹出队头元素,为当前点
x, y = q.popleft()
# 更新当前连通块的价值
cur_value += int(grid[x][y])
for dx, dy in DIRECTIONS:
nxt_x, nxt_y = x+dx, y+dy
# 若下一个点要加入队列,应该满足以下三个条件:
# 1.没有越界
# 2.在grid中值为"1"或"2"
# 3.尚未被检查过
if 0 <= nxt_x < n and 0 <= nxt_y < m: # 越界判断
# 在grid中为"1"或"2",尚未被检查过
if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
q.append([nxt_x, nxt_y]) # 入队
check_list[nxt_x][nxt_y] = 1 # 标记为已检查过
# BFS搜索完成,更新本连通块的价值
ans = max(cur_value, ans)
print(ans)
解法二:DFS
# 题目:2023B-寻找价值最大的矿堆
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:DFS
# 代码看不懂的地方,请直接在群上提问
# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]
# 输入地图
grid = list()
while True:
row = input()
if len(row) == 0:
break
grid.append(row)
# 根据地图获得行数、列数
n, m = len(grid), len(grid[0])
# 答案变量,用于记录价值最大的矿堆
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过,1表示检查过了
check_list = [[0] * m for _ in range(n)]
# 构建DFS递归函数
def dfs(check_list, x, y):
# 声明变量cur_value为全局变量,表示当前DFS的矿堆价值
global cur_value
# 将点(x, y)标记为已检查过
check_list[x][y] = 1
# 更新当前连通块的价值
cur_value += int(grid[x][y])
for dx, dy in DIRECTIONS:
nxt_x, nxt_y = x + dx, y + dy
# 若下一个点继续进行dfs,应该满足以下三个条件:
# 1.没有越界
# 2.在grid中值为"1"或"2"
# 3.尚未被检查过
if 0 <= nxt_x < n and 0 <= nxt_y < m: # 越界判断
# 在grid中为"1"或"2",尚未被检查过
if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
# 可以进行dfs
dfs(check_list, nxt_x, nxt_y)
# 最外层的大的双重循环,是用来找DFS的起始搜索位置的
for i in range(n):
for j in range(m):
# 找到一个"1"或"2",并且这个"1"或"2"从未被搜索过:那么可以进行DFS的搜索
# 1. 值得是"1"或"2" 2. 没被搜索过
if grid[i][j] != "0" and check_list[i][j] == 0:
# 初始化当前矿堆的价值为0
cur_value = 0
dfs(check_list, i, j)
# BFS搜索完成,更新最大矿堆的价值
ans = max(ans, cur_value)
print(ans)
时空复杂度
时间复杂度:O(MN)
。
空间复杂度:O(MN)
。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
-
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)
-
绿色聊天软件戳 od1336
了解更多