#P8462. 「REOI-1」奶油蛋糕

「REOI-1」奶油蛋糕

题目背景


早餐时间过后,小不点们都前往操场接受基础训练课程,威廉便趁机占据厨房了。
他在军服上披围裙,头上绑三角巾,还将清早从市场采买回来的大量材料摆到桌上。
接着,威廉烤了大量的奶油蛋糕。

威廉把奶油蛋糕摆放到桌子上,珂朵莉闻到了蛋糕的香味,迫不及待地扑到了餐桌前享受着这份饕餮盛宴,然而蛋糕的制作,似乎还差了那么最后一步……
“等一等哦,我还没有挤上奶油呢。”威廉说着,拿起了裱花袋。

可饥肠辘辘的珂朵莉哪里等得起全部的奶油都给挤好?
正当威廉还在忙着挨个给蛋糕挤上白花花的奶油的时候,珂朵莉已经偷偷的拿起了一块蛋糕……

题目描述

在桌子上的蛋糕可以看作是一个无限大的平面直角坐标系,每一个蛋糕都位于坐标系的整点上。

每一分钟,威廉会给每个蛋糕都涂上若干层奶油,规则如下:如果蛋糕连续第 ii 次没有被珂朵莉吃到,那么就会在蛋糕上挤上 ii 层奶油。

每次在威廉挤完所有蛋糕的奶油后,珂朵莉会拿起一块蛋糕,把这个蛋糕上的奶油给吃掉一层。特别的,如果珂朵莉吃掉了蛋糕上的一层奶油,威廉马上会贴心的再次给这个蛋糕补上一层,且不计入连续没有被吃到的次数里(即下一次的 ii 依旧为 11 )。

由于蛋糕太多,珂朵莉实在不知道从何下手,所以她决定按照移动的吃法进行试吃。
总共 mm 个分钟,珂朵莉的吃蛋糕序列可以用一个长度为 mm 的字符串表达。第 tt 个字符可能为 NSWE分别表示珂朵莉在第 t+1t+1 分钟会吃掉第 tt 分钟吃掉蛋糕的上,下,左,右方位的蛋糕。
珂朵莉第 11 个分钟会拿起位于点 (x,y)(x,y) 的蛋糕,因为蛋糕目前没有被挤上奶油,所以珂朵莉既不会进行试吃,威廉也不会立刻给她补上奶油。

珂朵莉想知道在 mm 分钟后,这些蛋糕在最后都还剩多少层奶油。

本题中的上和右分别表示 yy 轴正方向和 xx 轴正方向。


简要题面:

有一个 n×nn\times n 的地块,一个连续 ii 分钟没人经过的地面在第 ii 分钟会落上 ii 个单位的灰,有人经过时不会落灰但灰也不会清零,在人走后第一分钟又会落上一个单位的灰,以此类推。有一个人在这个 n×nn\times n 的范围内移动,他的移动轨迹可以描述为一个由 N,S,W,E\text{N,S,W,E} 组成的字符串,每个字母分别表示上、下、左、右。这个人一开始在点 (x,y)(x,y),每一分钟移动一步。

求最后每一个位置上落下的灰的量。

保证这个人没有超过移动的范围。

输入格式

第一行四个正整数 n,m,x,yn,m,x,y,含义如题面所示,其中 x,yx,y 表示横纵坐标,不是数组下标。
第二行一个长度为 mm 的字符串,表示珂朵莉的移动序列。

输出格式

nn 行,每行 nn 个数,第 ii 行的第 jj 个数表示坐标 (j,ni+1)(j,n-i+1) 上的灰的数量

5 4 1 1
NENW
10 10 10 10 10 
10 10 10 10 10 
10 6 10 10 10 
4 4 10 10 10 
6 10 10 10 10 

7 14 1 1
NENENENENESSSS
105 105 105 105 105 105 105 
105 105 105 105 55 61 105 
105 105 105 49 51 69 105 
105 105 51 49 105 79 105 
105 61 55 105 105 91 105 
79 69 105 105 105 105 105 
91 105 105 105 105 105 105 

10 70 2 2
NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS
2485 2485 2485 2485 2485 2485 2485 2485 2485 2485 
2485 1407 1205 1267 2485 2485 2485 2485 2485 2485 
2485 1435 1281 1167 2485 2485 2485 2217 2281 2347 
2485 1465 2485 1255 1041 2485 2485 2155 2485 2415 
1557 1497 2485 2485 969 1177 2485 1733 1807 2485 
1471 1531 1315 907 935 1267 2485 1473 1647 2485 
1631 2485 2485 1357 1381 1407 1435 1499 1645 2485 
2021 2347 2485 2485 2485 2485 1465 1497 2485 2485 
2087 2415 2485 2485 2485 2485 2485 2485 2485 2485 
2485 2485 2485 2485 2485 2485 2485 2485 2485 2485 

5 4 2 1
NENW
10 10 10 10 10 
10 10 10 10 10 
10 10 6 10 10 
10 4 4 10 10 
10 6 10 10 10 

提示

本题 y 轴朝上,x 轴朝右,样例输出中的左下角表示 (1,1)(1,1),第一分钟珂朵莉在初始点处,第二分钟移动到相应的位置,第 m+1m+1 分钟移动到最后一个点,但是总共只有 mm 分钟,因此最后一个点不受移动的影响


样例 1 解释:

珂朵莉的移动路径为 $(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$,共 44 分钟。

对于第 11 分钟,(1,1)(1,1) 奶油层数不变,其余点被挤上了 11 层奶油。

对于第 22 分钟,(1,2)(1,2) 奶油层数不变,(1,1)(1,1) 被挤上了 11 层奶油,其余点挤上 22 层奶油。

对于第 33 分钟,(2,2)(2,2) 奶油层数不变,(1,1)(1,1) 挤上 22 层奶油,(1,2)(1,2) 挤上 11 层奶油,其余点挤上 33 层奶油。

对于第 44 分钟,(2,3)(2,3) 奶油层数不变,(1,1)(1,1) 挤上 33 层奶油,(1,2)(1,2) 挤上 22 层奶油,(2,2)(2,2) 挤上 11 层奶油,其余点挤上 44 层奶油。

注意最后珂朵莉移动到了 (1,3)(1,3),但是时间只有 44 分钟,所以实际上不会对 (1,3)(1,3) 造成影响。初始点不一定在 (1,1)(1,1)

1n50,1m10001\le n\leq 50,1\leq m\le 1000