← 返回题目列表

AtCoder · joi2016ho_d

D. 领土

中文机器翻译题面 查看原题

配点: 100 点

您生活在一个城市,许多道路南北延伸很长,许多道路东西延伸很长。彼此相邻 2 两条南北向道路之间的距离为 1 公里。还有,相邻的 2 两条东西向道路之间的距离也是 1 公里。

这个城市有市政厅。 1 有一个。市政厅所在的十字路口 表示为 (0, 0) 。这个城市的十字路口 使用 2 整数 i, j 的交叉点 表示为 (i, j) 。也就是说,交集(i, j) 表示交叉点。 从 (0, 0) 向东 i 公里(i < 0 向西 -i 公里),向北 j 公里(j < 0 向南 -j km) 表示高级位置处的交叉路口。

在市政厅里,有一个名叫乔伊的女孩。 1 我有两只狗。喜悦你 K 我制定了一天的步行计划。步行计划如下。

  • K 第一天早上,乔伊过马路。 (0, 0) 。喜悦就在十字路口 标记 (0, 0) 。 除了(0, 0) 之外,没有任何由 Joy 标记的交叉点。
  • K 每天中午散步。1 每天步行是 它由 N 步骤组成。在每一步中,从一个路口移动到下一个路口并标记目的地。无论哪天,乔伊每天中午的移动方式都是恒定的。
  • 完成白天的旅程后,在当前所在的路口睡觉直到第二天早上。在市政厅 K 几天来,人们对乔伊通过行走创造的领地进行了很多讨论。4 交叉路口 Joy-kun 全部都是 (a, b), (a + 1, b), (a + 1, b + 1), (a, b + 1) 当标记超过 1 次时,4 两个路口围成的区域属于Joy的领地。

您已经创建了一个程序,可以根据 Joy 的行走计划计算属于 Joy 领地的地块数量。 决定这样做。

这座城市的道路很长,南北和东西方向都有足够的道路,乔伊走路永远不会到达道路边缘或城市边缘。

課題

给定 Joy 的行走计划,编写一个程序来计算属于 Joy 领土的地块数量。


入力

从标准输入读取以下输入。

  • 1 在线 2 整数 写入 N, K 以空格作为分隔符。这就是每天的步行 N 次 步行计划由步骤组成。 K 代表持续数天。
  • 2 线是长度 写入 N 字符串 给出 S 。字符串 从 S 左侧开始 p 文字目 (1 \leqq p \leqq N) 字符 C_p 是 它仅由 E,N,W,S 。这些字符代表以下含义: 如果
    • 文字 C_p 是 在 E ,那么 第p 步表示移动到东边相邻的路口。 第
    • 文字 C_p 是 在 N ,那么 第p 步表示向北移动到下一个路口。 第
    • 文字 C_p 是 在 W ,那么 第p 步表示移动到西边的相邻路口。 第
    • 文字 C_p 是 在 S ,那么 第p 步表示移动到南边旁边的路口。 在这里,交点(i, j),东、北、西、南的交点是 (i + 1, j),交差点 (i, j + 1),交差点 (i - 1, j),交差点 (i, j - 1) 。

出力

属于 Joy 领土的部分数量被输出到标准输出。 1 行。


制限

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq K \leqq 1\,000\,000\,000.

小課題

小課題 1 [5 点]

满足以下条件。

  • N \leqq 50.
  • K = 1.

小課題 2 [10 点]

  • K = 1 满意。

小課題 3 [23 点]

  • N \leqq 50 满意。

小課題 4 [62 点]

没有其他限制。


入力例 1

12 1
EENWSEEESWWS

出力例 1

3

在此输入示例中,步行是 它将持续 1 天。1 当天,Joy从市政厅出发,移动如下图所示。

黑色圆圈是Joy已标记的路口,白色圆圈是Joy未标记的路口,双圆圈是与市政厅的路口,数字代表每一步。 在

ジョイ君の移動経路

入力例 1 中,下图阴影区域 3 部分属于 Joy 的领地。

入力例 <var>1</var> におけるジョイ君の縄張り


入力例 2

12 2
EENWSEEESWWS

出力例 2

7

入力例 2 所以步行是 它将持续 2 天。每天的输入路径示例 与 1 相同。当行走完成后,下图中阴影区域所指示的区域 7 部分属于 Joy 的领地。

入力例 <var>2</var> におけるジョイ君の縄張り

入力例 2 是一个小任务 1 和小作业 请注意,不满足 2 约束。 在


入力例 3

7 1
ENNWNNE

出力例 3

0

入力例 3 中,没有任何部分属于Joy的领土。


入力例 4

16 5
WSESSSWWWEEENNNW

出力例 4

21

入力例 4 是一个小任务 1 和小作业 请注意,不满足 2 约束。 在