题解

思路

不等待时，到达 $(i,j)$ 需要 $i+j$ 秒。把额外等待秒数记为 $w$，则状态的真实时刻为 $i+j+w$。由于只有 $r$ 次射击，若存在可行路线，总能在额外等待不超过 $r$ 次的范围内找到最短路线。

做法

无影响射击

若所有射击时刻都晚于 $n+m$，任选一条不等待的最短单调路径即可，答案是 $n+m$。

小规模时间展开

按秒做广度优先动态规划，枚举等待、向下和向右三种动作，并删除当前时刻被击中的位置。

满分算法

设 $dp_{i,j,w}$ 表示能否在时刻 $i+j+w$ 安全到达 $(i,j)$。若该时刻该行或该列被射击，状态不可用；否则它可以从 $dp_{i-1,j,w}$、$dp_{i,j-1,w}$ 或 $dp_{i,j,w-1}$ 转移而来。终点第一个可达的 $w$ 给出最短时间 $n+m+w$。

正确性说明

三个前驱分别对应题目允许的向下、向右和等待动作，且状态时刻都恰好相差一秒。每个状态在转移后检查该秒结束时的射击，因此恰好排除所有死亡路线。反之，任意合法路线按每一步动作都对应一条 DP 转移，所以所有合法路线都会被计入。

复杂度

满分算法时间和空间复杂度均为 $O(nmr)$；小规模时间展开复杂度为 $O((n+m+r)nm)$。