P11394 [JOI Open 2019] 病毒实验 / Virus Experiment

**译自 [JOI Open 2019](https://contests.ioi-jp.org/open-2019/index.html) T3 「ウイルス実験」** JOI 公司研究了新型病毒 `JOI virus`。JOI 公司希望通过用该病毒影响在 IOI 岛的动物做实验。 IOI 岛呈矩形。有 $R-1$ 条从西向东的平行道路，和 $C-1$ 条从北向南的平行道路。她们将岛分割成 $RC$ 个部分。每部分只有一只动物。我们称居住在北部第 $i$，西部第 $j$ 部分的动物为 `动物(i,j)`（$1\le i\le R$，$1\le j\le C$）。 在 IOI 岛上，一天有 $M$ 个时间段。我们管第 $k$ 个叫 `时间段k`。风总是从某方向吹来：北方，南方，东方和西方。基于时间段，风向可能改变。如果时间段相同，风向总是不变，这和在哪一天无关。 每只动物有一个状态 `抵抗力`。动物 $(i,j)$ 的抵抗力表示为一个非负整数 $U_{i,j}$。 - 如果 $U_{i,j}=0$,说明动物 $(i,j)$ 有很高的抵抗力，使得它不被 JOI virus 感染。 - 如果 $U_{i,j}$ 是一个正整数，说明动物 $(i,j)$ 可能被感染。如果下面条件连续成立了 $U_{i,j}$ 时间段，则他/她会从下一个时间段开始被感染。 -- 从风向处相邻的动物已经被传染。 注意最后一个时间段和下一天的第一个时间段是连续的。 为了实验，我们希望至少感染 $1$ 只动物，但是我们不希望感染过多的动物。在开始，我们选择一只作为第一个被感染的。我们不能选择 $U_{i,j}=0$ 的动物 $(i,j)$ 作为第一个被感染的个体。 给定每个时间段的风向和每只动物的抵抗力。编写程序计算经过了 $10^{100}$ 天后最少被感染了个体数，和达成此目标刚开始能选择的个体有几种。

第 $1$ 行三个整数 $M,R,C$。 第 $2$ 行一个整数 $D$。 第 $3\sim3+R-1$ 行，每行 $C$ 个整数。第 $i-3+1$ 行第 $j$ 列的数表示 $U_{i,j}$。 $D$ 是长 $M$ 的字符串表示风向。D 包含 $4$ 种字符：$\texttt N$, $\texttt S$, $\texttt W$, $\texttt E$。分别表示北南西东。第 $k$ 个字符（$1\le k\le M$）表示第 $k$ 个时间段的风向。

第 $1$ 行一个数表示最少被感染个体数。 第 $2$ 行一个数表示使得被感染的个体最少，初始时有几种选法。

#### 样例解释： 让我们考虑选择动物 $(3,1)$ 作为初始被感染个体的情况。 对于动物 $(2,1)$，在第 $1$ 天的时间段 $1$，刮南风，且南边相邻动物已经被感染，所以他/她会从第 $1$ 天的时间段 $2$ 被感染。 对于动物 $(3,2)$，在第 $1$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $1$ 天的时间段 $3$ 被感染。 对于动物 $(1,1)$，在第 $1$ 天的时间段 $6$，刮南风，且南边相邻动物已经被感染，且在第 $2$ 天的时间段 $1$，刮南风，且南边相邻动物已经被感染，所以他/她会从第 $2$ 天的时间段 $2$ 被感染。 对于动物 $(1,2)$，在第 $2$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $2$ 天的时间段 $3$ 被感染。 对于动物 $(1,3)$，在第 $3$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $3$ 天的时间段 $3$ 被感染。 对于动物 $(2,3)$，在第 $3$ 天的时间段 $3$，刮北风，且北边相邻动物已经被感染，所以他/她会从第 $3$ 天的时间段 $4$ 被感染。 对于动物 $(3,3)$，在第 $4$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，且在第 $4$ 天的时间段 $3$，刮北风，且北边相邻动物已经被感染。所以他/她会从第 $4$ 天的时间段 $4$ 被感染。 没有更多动物会被感染。所以当选择 动物 $(3,1)$ 作为初始被感染者时，经过 $10^{100}$ 天，$8$ 只动物会被感染。 不论选哪只动物作为初始被感染者，我们都无法使得 $10^{100}$ 天后被感染的动物数量小于 $8$，所以输出的第一行是 $8$。如果我们选择动物 $(1,1)$，$(1,2)$，$(1,3)$，$(2,1)$，$(2,3)$，$(3,1)$，$(3,2)$ 或 $(3,3)$ 作为初始被感染者，在 $10^{100}$ 天后被感染的个数都是 $8$。所以第二行应当输出 $8$。 这个样例满足 `子任务1` 的约束条件。 #### 数据范围： $1\le M\le 10^5$，$1\le R\le 800$，$1\le C\le 800$。 $D$ 是一个长度为 $M$ 的字符串，只包含 $\texttt N$, $\texttt S$, $\texttt W$, $\texttt E$。 $0\le U_{i,j}\le 10^5$（$1\le i\le R$，$1\le j\le C$）。 至少有一对 $(i,j)$ 满足 $1\le U_{i,j}$（$1\le i\le R$，$1\le j\le C$）。 #### 子任务： 1. （14 分）$D$ 只包含 $\texttt W$ 和 $\texttt E$。 2. （6 分）$1\le W\le 50$，$1\le C\le 50$。 3. （80 分）无额外约束。