AT_joi2016ho_d.縄張り (Territory)

你居住的城市由许多长长的南北向和东西向道路交织而成。相邻的南北向道路之间的间距是 $1$ 公里，东西向道路之间的间距也是 $1$ 公里。

市政府坐落在一个交叉口，标记为 $(0, 0)$。每个交叉口可以用两个整数 $(i, j)$ 来表示，即从交叉口 $(0, 0)$ 出发，向东走 $i$ 公里（$i < 0$ 则向西走），向北走 $j$ 公里（$j < 0$ 则向南走）的位置。

乔伊是一只养在市政府的狗，它计划了一个为期 $K$ 天的散步活动。计划如下：

• 第一天早晨，乔伊从交叉口 $(0, 0)$ 出发，并在那里做标记。除了 $(0, 0)$，没有其他交叉口被标记。
• 乔伊每天中午散步，由 $N$ 步组成。每一步移动到相邻的交叉口，并做标记。乔伊每天的散步路线相同。
• 散步结束后，乔伊在当前交叉口休息到第二天早上。市政府讨论了乔伊的散步所覆盖的领地定义为：如果四个交叉口 $(a, b), (a + 1, b), (a + 1, b + 1), (a, b + 1)$ 都被标记过，则该区域属于乔伊的领地。

你的任务是根据乔伊的散步方案，计算乔伊领地所包含的区域数量。

由南北向和东西向的道路组成的城市非常大，所以乔伊在散步途中不会到达道路的尽头或城市的边界。

输入包含以下内容：

• 第一行包括两个整数 $N, K$，分别表示每天散步有 $N$ 步，散步计划持续 $K$ 天。
• 第二行是一个长度为 $N$ 的字符串 $S$，其中每个字符 $C_p$ （$1 \leq p \leq N$）可以是 'E'（东）、'N'（北）、'W'（西）、'S'（南）之一：
  • 'E' 表示向东走一步。
  • 'N' 表示向北走一步。
  • 'W' 表示向西走一步。
  • 'S' 表示向南走一步。
    这里，交叉口 $(i, j)$ 的东邻、北邻、西邻、南邻分别为 $(i + 1, j)、(i, j + 1)、(i - 1, j)、(i, j - 1)$。

输出一个整数，表示乔伊的领地中包含的区域总数。

任务

给你乔伊的散步计划，编写程序计算属于乔伊领地的区域数量。

限制

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

• $1 \leq N \leq 100,000$
• $1 \leq K \leq 1,000,000,000$

子任务

子任务 1 [5 分]

满足以下条件：

• $N \leq 50$
• $K = 1$

子任务 2 [10 分]

满足以下条件：

• $K = 1$

子任务 3 [23 分]

满足以下条件：

• $N \leq 50$

子任务 4 [62 分]

无额外限制。

本翻译由 AI 自动生成