Tag

请你返回你在初始位置可以停留的最多分钟数且停留完这段时间后你还能安全到达安全屋。

如果无法实现请你返回

注意如果你到达安全屋后火马上到了安全屋这视为你能够安全到达安全屋。

输入grid

[[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]输出3解释上图展示了你在初始位置停留

输入grid

[[0,0,0,0],[0,1,2,0],[0,2,0,0]]输出-1解释上图展示了你马上开始朝安全屋移动的情形。

火会蔓延到你可以移动的所有格子所以无法安全到达安全屋。

所以返回

输入grid

[[0,0,0],[2,2,0],[1,2,0]]输出1000000000解释上图展示了初始网格图。

注意由于火被墙围了起来所以无论如何你都能安全到达安全屋。

所以返回

109

秒后出发仍能到达安全屋说明人员对逃走路线的访问要比火势更快。

那么人员在更早的时间点

假设存在某个判定函数

在人员移动路线中“回头路”是没有意义的因此人员对每个点的访问次数最多为一次。

同时不考虑墙的阻拦火势也最多在不超过棋盘大小的时间内完全蔓延。

接下来考虑如何实现

BFS按照「先火后人」的方式同步模拟「火势蔓延」和「人员移动」过程。

普通位置只要火势蔓延到那么人将无法移动到此处安全屋位置需要判断是否与火势同一时刻到达。

update

经过上述解法我们发现存在大量重复计算例如每次唯一确定的“火势蔓延”过程以及每次根据最新起始火势由延迟出发时间

所决定进行的“人员移动”过程都是不必要的可通过比较双方到达时间来求解。

pg分别预处理出「火势」和「人员」到达每个网格的最早时间。

其中火势蔓延唯一确定而人员的预处理是在不考虑火势的情况下进行。

进行分情况讨论

火和人都能到达安全屋。

即使不考虑人员中途被火影响人员可能无法按照最佳路线前往安全屋的情况下火也比人要更早到达安全屋返回

理想情况下人比火更早到达安全屋但存在「人火同时到达」、「人员中途被烧」或「通路被火拦截」等问题需要进一步分情况讨论

人员只能从

两个位置之一到达安全屋这两个属于普通位置不允许人和火同时到达因此可以将「对特殊位置安全屋」的讨论转为「对普通位置」的讨论

人比火更早到达该位置返回

在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。

如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode

合集新基地