#P4983. 遛狗

    ID: 4083 传统题 1000ms 64MiB 尝试: 18 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-坐标变换等价类划分向下取整与向上取整区间合并同向双指针

遛狗

题目描述

JK 生活的地区可以看作一个由无限延伸、相互垂直的道路构成的网格。我们可以将路口抽象为二维平面上的整点坐标 (i,j)(i, j)。路口 (i,j)(i, j) 表示从原点 (0,0)(0, 0) 向东移动 ii 公里、向北移动 jj 公里到达的位置(当 ii 或 jj 为负数时,分别表示向西或向南)。JK 的家位于 (0,0)(0, 0)。

JK 为他的爱犬制定了一个为期 KK 天的遛狗计划,具体如下:

  • 第一天:早上,JK 从家 (0,0)(0, 0) 出发。他的狗在 (0,0)(0, 0) 处留下了一个标记。此时,仅有 (0,0)(0, 0) 这一个路口被标记。

  • 每日散步:在 KK 天中的每一天,JK 都会进行一次固定的散步。一次散步由 NN 次移动组成。每次移动都是从一个路口到相邻路口,并在到达的新路口留下标记。这 NN 次移动的序列每天都是完全相同的。

  • 跨天移动:每天白天的散步结束后,JK 会在当前所在的路口休息,直到第二天早上再从该路口开始新一天的散步。

领地定义 当四个路口 (a,b)(a, b)、(a+1,b)(a + 1, b)、(a+1,b+1)(a + 1, b + 1) 和 (a,b+1)(a, b + 1) 均被标记过(至少一次)时,这四个路口围成的 1×11\times1 正方形区域就被视为 JK 的狗的领地。

请你编写一个程序,计算在 KK 天的计划结束后,JK 的狗总共获得了多少个单位的领地。

注意:可以认为地图足够大,JK 在遛狗途中不会到达边界。

输入格式

第一行包含两个整数 NN 和 KK,分别表示每天散步的移动次数和计划的总天数。

第二行是一个长度为 NN 的字符串 SS,描述了单日散步的移动序列。字符串中的每个字符代表一次移动:

  • E:向东移动,从 (i,j)(i, j) 到 (i+1,j)(i + 1, j)。
  • N:向北移动,从 (i,j)(i, j) 到 (i,j+1)(i, j + 1)。
  • W:向西移动,从 (i,j)(i, j) 到 (i−1,j)(i - 1, j)。
  • S:向南移动,从 (i,j)(i, j) 到 (i,j−1)(i, j - 1)。

输出格式

输出一个整数,代表 JK 的狗最终获得的领地总数。

12 2
EENWSEEESWWS
7

数据范围

1≤N≤1051\le N\le10^5,1≤K≤1091\le K\le 10^9。