#3155. 「JOI Open 2019」病毒实验

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 JOI Open 2019 T3 「ウイルス実験 / Virus Experiment

你知道「净是一些鬼畜发明公司」(Just Odd Inventions Co., Ltd.)吗?这家公司就是发明一些鬼畜玩意的。现在我们就叫它 JOI 公司。

JOI 公司开发了一种新型病毒——「JOI 病毒」。JOI 公司想要通过用 JOI 病毒感染 IOI 岛上的居民的方式做一次病毒实验。

IOI 岛是一个矩形,从东向西有 R-1 条互相平行的街道,从北向南有 C-1 条互相平行的街道。它们把岛划分为 RC 个区域。每个区域只住着一个居民,我们称住在从北数第 i 区域,从西数第 j 个区域的居民为居民 (i,j)

在 IOI 岛上,一天共有 M 个时间段。我们称第 k 个时间段为时段 k 。风总是从东西南北四个方向吹来,风向取决于时段。如果时段相同,则风向相同,与日期无关。

每个居民都有一个抵抗力。居民 (i,j) 的抵抗力用一个非负整数 U_{i,j} 表示。

  • 如果 U_{i,j}=0 ,表示居民 (i,j) 的抵抗力很高,并且这位居民不会感染 JOI 病毒;
  • 如果 U_{i,j}>0 ,表示居民 (i,j) 可能会感染 JOI 病毒。如果以下情况持续了 U_{i,j} 个时段,这位居民就将在下一个时段感染 JOI 病毒:
    • 住在风吹来方向且与这位居民相邻的居民感染了 JOI 病毒。
      注意一天最后一个时段和下一天第一个时段是连续的。

为了完成实验,我们想要至少感染一位居民,但是我们不想感染太多的居民。在初始的时候,我们选择一位居民作为第一个被感染的人,然后使他感染 JOI 病毒。我们不能感染抵抗力为 0 的居民。

给定每一个时段的风向,写一个程序计算在 10^{100} 天之后至少会有多少居民被感染,和达到这个最小值选择初始感染者的方案数。

输入格式

第一行三个正整数 M,R,C ,意义如题目描述。

接下来一行一个长为 M 的字符串 D ,表示一天中每个时段的风向。 D 中只包含 NSWE 四种字符。第 k\ (1\le k\le M) 个字符表示时段 k 风的来向N 代表风从北吹来,S 表示风从南方吹来,W 表示风从西吹来,E 表示风从东吹来。

接下来 R 行,每行 C 个整数。第 i 行第 j 列的整数 U_{i,j} 表示居民 (i,j) 的抵抗力。

输出格式

输出两行。第一行表示在 10^{100} 天之后至少能感染居民的数量。第二行输出达到这个最小值的情况下选择初始感染者的方案数。

样例

样例输入 1

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

样例输出 1

8
8

样例说明 1

考虑当居民 (3,1) 是初始感染者的情况。

  • 对于居民 (2,1) ,在第 1 天的时段 1 ,风从南方吹来,并且位于他南方的相邻居民(即居民 (3,1) )已经感染了病毒,因此这位居民将在第 1 天的时段 2 感染;
  • 对于居民 (3,2) ,在第 1 天的时段 2 ,风从西方吹来,并且位于他西方的相邻居民(即居民 (3,1) )已经感染了病毒,因此这位居民将在第 1 天的时段 3 感染;
  • 对于居民 (1,1) ,在第 1 天的时段 6 ,风从南方吹来,并且位于他南方的相邻居民(即居民 (2,1) )已经感染了病毒,在第 2 天的时段 1 ,风从南方吹来,并且位于他南方的相邻居民(即居民 (2,1) )已经感染了病毒,因此这位居民将在第 2 天的时段 2 感染;
  • 对于居民 (1,2) ,在第 2 天的时段 2 ,风从西方吹来,并且位于他西方的相邻居民(即居民 (1,1) )已经感染了病毒,因此这位居民将在第 2 天的时段 3 感染;
  • 对于居民 (1,3) ,在第 3 天的时段 2 ,风从西方吹来,并且位于他西方的相邻居民(即居民 (1,2) )已经感染了病毒,因此这位居民将在第 3 天的时段 3 感染;
  • 对于居民 (2,3) ,在第 3 天的时段 3 ,风从北方吹来,并且位于他北方的相邻居民(即居民 (1,3) )已经感染了病毒,因此这位居民将在第 3 天的时段 4 感染;
  • 对于居民 (3,3) ,在第 4 天的时段 2 ,风从西方吹来,并且位于他西方的相邻居民(即居民 (3,2) )已经感染了病毒,在第 4 天的时段 3 ,风从北方吹来,并且位于他北方的相邻居民(即居民 (2,3) )已经感染了病毒,因此这位居民将在第 4 天的时段 4 感染。

这样就没有再多的居民会感染 JOI 病毒了。于是,当我们选择居民 (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

样例输入 2

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

样例输出 2

3
3

样例说明 2

这组样例满足子任务 1 的限制。

数据范围与提示

对于全部数据, 1\le M\le 10^5,1\le R,C\le 800,0\le U_{i,j}\le 10^5 ,保证 D 字符串长度为 M 并且只包含 NSWE 四种字符,并且保证至少有一个 U_{i,j}\ge 1\ (1\le i\le R,1\le j\le C)

具体子任务附加限制及分值如下:

  • 子任务 1 14 分): D 中只包含 WE 两种字符;
  • 子任务 2 6 分): 1\le R,C\le 50
  • 子任务 3 80 分):无附加限制。