网站建设公司墨子网络,百度域名续费,凡客网站官网,项目经理背景
记录2023-10-21 晚华为OD三面的手撕代码题#xff0c;当时没做出来#xff0c;给面试官说了我的想法#xff0c;评价#xff1a;解法复杂了#xff0c;只是简单的动态规范 或 广度优先算法#xff0c;事后找资料记录实现方式。
题目 腐烂的橘子 问题描述#xff…背景
记录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 flag0 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 1flag2:itime -1breakitime 1print(结果,itime)实现二动态规范
求解思路
问题抽象为 求每个点 到最近的 坏的橘子的 最短距离构造初始距离矩阵约定 0、坏橘子 inf、永远不坏 row*col、好橘子最大距离 做两次 扫描更新最短距离得到整体最短距离找到 永不更新的点
代码实现
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-10:if M_status[ir][ic-1]1M_status[ir][ic]:M_status[ir][ic] M_status[ir][ic-1]1if ir-10:if M_status[ir-1][ic]1M_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 ic1col:if M_status[ir][ic1]1M_status[ir][ic]:M_status[ir][ic] M_status[ir][ic1]1if ir1row:if M_status[ir1][ic]1M_status[ir][ic]:M_status[ir][ic] M_status[ir1][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 vmaxMAXTIME: # 还存在新鲜的橘子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]]
结果验证 参考资料
矩阵广度优先搜索动态规划
