U537680 身怀利器，杀心自起

## MC模组系列1 #### 武士刀

武士刀有许多种攻击方式，具体而言如下： + 平斩：普通攻击，攻击距离$\tt e$，造成$\tt t$点伤害 + 冲刺斩：向前冲刺$\tt w$格，撞到墙则立即停止，对道路上的人造成$\tt k$点伤害，有一定冷却时间$\tt c$ + 回旋斩：回旋攻击，对周围$\tt f$格的人造成$\tt p$点伤害，此处周围$\tt f$格指的是以自身为中心的边长为$\tt f$的正方形，此处保证$\tt f$为奇数 + 触地斩：将剑砸入地面，产生振荡，对周围$\tt v$格的人造成$\tt w$点伤害，此处周围$\tt v$格指的是以自身为中心的边长为$\tt v$的正方形，此处保证$\tt v$为奇数。而如果在空中向下坠落到地面时触发触地斩，则本次攻击范围变成$\tt z$ + 跳斩：从上往下掉落的时候无论何种攻击，伤害都变为原来的1.5倍 + 上闪：触发时传送到空中，有一定冷却时间$\tt d$，可与跳斩配合，值得注意的是，上闪后立刻触发冲刺斩无法攻击到敌人，但其它方式可以直接落地造成攻击，而除了上闪，没有其他方式可以抵达空中触发跳斩 组合技： + 三连斩：原地触发回旋斩然后立刻冲刺斩，会触发三连斩，就是连续三次冲刺斩，方向自定 + 击退斩：向后冲刺斩，然后回旋斩，在冲刺斩回去，触发平斩即可触发击退斩，将敌人击退$\tt h$格，若是在冲刺回去后触发回旋斩，则将攻击到的所有敌人都击退$\tt h$格，击退是指把敌人沿面对方向的反方向强制移动 现在有一个$\tt n \times m$的二维迷宫，有一群僵尸在里面呆着，而你也在里面的$\tt (x_0,y_0)$处被包围。现在，你手里有一把武士刀，请用这把武士刀杀出重围。请杀完所有僵尸再离开，相信通过这把武士刀，你必定能以一己之力对抗百万大军 现在，告诉你每只僵尸的状态，每种攻击耗时都是1秒，移动速度1格每秒，现在，请给出杀死所有僵尸的最短时间

第一行，两个数，$\tt n,m$，表示迷宫的长和宽 接下来给出一个$\tt n \times m$的迷宫地图，其中`1`表示墙壁，`0`表示空地。 接下来一个数$\tt q$表示僵尸的数量 接下来$\tt q$行，每一行三个数加上一个字符，分别是$\tt x_i,y_i,b_i,f_i$，$\tt (x_i,y_i)$表示第$\tt i$只僵尸的坐标，保证所在位置不为墙壁，$\tt b_i$表示第$\tt i$只僵尸的血量，$\tt f_i$表示第$\tt i$只僵尸面向的方向，上`N`，下`S`，左`W`，右`E` 下面一行，两个数$\tt e,t$，表示平斩攻击距离和伤害 下面一行，三个数$\tt w,k,c$，表示冲刺斩的冲刺距离、伤害和冷却时间 下面一行，两个数$\tt f,p$，表示回旋斩的攻击范围和伤害 下面一行，三个数$\tt v,w,z$，表示触地斩攻击范围、攻击伤害、落地触地斩攻击范围 下面一行，一个数$\tt d$，表示上闪冷却时间 下面一行，一个数$\tt h$，表示击退斩击退格数 最后一行，两个整数$\tt x_0,y_0$表示你的初始坐标

一个数$\tt t$，表示最短时间

$\tt 1 \le n,m \le 20$ $\tt 1 \le q \le 10^6$（没毛病，百万大军） [题解](https://www.luogu.com.cn/paste/co0ej6v9)