华为OD技术面试-最短距离矩阵(动态规划、广度优先)

背景

记录2023-10-21 晚华为OD三面的手撕代码题，当时没做出来，给面试官说了我的想法，评价：解法复杂了，只是简单的动态规范 或 广度优先算法，事后找资料记录实现方式。

题目

腐烂的橘子
问题描述：
在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
【每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。】
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。【如果不可能，返回 -1。】
示例 1：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：[[2,1,1],[0,1,1],[1 ,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

实现一（广度优先）

求解思路

就按照题目描述，
（1）按照时间 线
（2）逐步 遍历所有的位置
（3）根据规则，如果有坏橘子，且四个正方向(东南西北)有好橘子，则更新之
（4）设计一个状态变量，记录当前时刻：是否有橘子腐败，如果无橘子腐败，是 全部好，还是全部坏，亦或者 好坏相间。

代码实现

testA = [[2,1,1],[1,1,0],[0,1,1]]
testB = [[2,1,1],[0,1,1],[1,0,1]]
testC = [[0,2]]M_position = testA
print(M_position)row = len(M_position)
col = len(M_position[0])
set_bad = []for ir in range(row):for jc in range(col):if M_position[ir][jc]==1:set_bad.append((ir, jc))
print(row, col)# 一次时间变更
def onetimeupndate():# 状态变量 # 0 无橘子# 1、全部新鲜# (1, 2) 好坏 混杂，且未 感染# 2、全部坏、# 3、坏感染flag = 0# 变更状态的坐标changed_set = []for ir in range(row):for jc in range(col):if M_position[ir][jc]==0:continue# 记录唯一状态if flag!=3:flag = (flag + M_position[ir][jc])/(1 if flag==0 else 2)# 坏橘子才更新if M_position[ir][jc]!=2 or ((ir, jc) in changed_set):continue# 遍历方向for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:ar_, bc_ = ir + i, jc + jif ar_<0 or ar_>=row or bc_<0 or bc_>=col:continueif M_position[ar_][bc_]==1:# 记录更新的坐标changed_set.append((ar_, bc_))# 标记状态flag = 3# 换橘子M_position[ar_][bc_]=2return flagitime = 0
while True:flag = onetimeupndate()print("当前次数",itime)print("状态变量",flag)print("最新结果",M_position)if flag!=3:if 1<flag<2:itime = -1breakitime +=1print("结果",itime)

实现二（动态规范）

求解思路

1. 问题抽象为 求每个点 到最近的 坏的橘子的 最短距离
2. 构造初始距离矩阵，约定：

0、坏橘子 inf、永远不坏 row*col、好橘子最大距离

3. 做两次 扫描，更新最短距离
4. 得到整体最短距离，找到 永不更新的点

代码实现

def calmintime(M_position):# 最短路径矩阵M_status = []# 尺寸信息row = len(M_position)col = len(M_position[0])MAXTIME = row * col# 初始矩阵for ir in range(row):for ic in range(col):if ic == 0:M_status.append([])if M_position[ir][ic] == 2: # 腐烂v = 0elif M_position[ir][ic] == 0: # 无v = infelif M_position[ir][ic] == 1: # 新鲜v = MAXTIME # 设为一个到不了的实数最大值M_status[ir].append(v)# 往左下遍历，比较右上两个方向for ir in range(row):for ic in range(col):if M_position[ir][ic]==0:continueif ic-1>=0:if M_status[ir][ic-1]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir][ic-1]+1if ir-1>=0:if M_status[ir-1][ic]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir-1][ic]+1# 往 右上遍历，比较左下两个方向for ir in reversed(range(row)):for ic in reversed(range(col)):if M_position[ir][ic]==0:continueif ic+1<col:if M_status[ir][ic+1]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir][ic+1]+1if ir+1<row:if M_status[ir+1][ic]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir+1][ic]+1# 最短距离vlist = []for ir in range(row):for ic in range(col):v = M_status[ir][ic]if not v is inf:vlist.append(v)if len(vlist)==0:return 0vmax = max(vlist)if vmax==MAXTIME: # 还存在新鲜的橘子return -1else:return vmaxtestA = [[2,1,1],[1,1,0],[0,1,1]]
testB = [[2,1,1],[0,1,1],[1,0,1]]
testC = [[0,2]]

结果验证

参考资料

矩阵（广度优先搜索）（动态规划）