luogu#P9945. [USACO21FEB] Clockwise Fence B

[USACO21FEB] Clockwise Fence B

题目描述

围绕 Farmer John 最大的草地的栅栏已经损坏了,如今他终于决定要换一个新的栅栏。

不幸的是,当 Farmer John 在铺设新栅栏时,一只巨大的蜜蜂突然出现,在他的草地上追着他跑,导致最后栅栏被沿着一条相当不规则的路径铺设。栅栏可以用一个字符串表示,每个字符为 N(north,北)、E(east,东)、S(south,南)、W(west,西)之一。每个字符表示一米长的一段栅栏。举例来说,如果字符串为 NESW,这表示栅栏从起点开始向北延伸 11 米,然后向东延伸 11 米,然后向南延伸 11 米,然后向西延伸 11 米,回到栅栏的起点。

栅栏的结束位置与开始位置相同,而这是栅栏的路径上唯一会被到达多次的位置(从而起始位置是唯一会被再次到达的位置,在栅栏结束之时)。结果,栅栏确实围起了一个草地上连通的区域,尽管这个区域可能形状十分奇特。

Farmer John 想要知道他铺设栅栏的路径是顺时针(当按字符串表示的顺序沿着栅栏的路径行走时被围起的区域位于右侧)还是逆时针(被围起的区域位于左侧)。

输入格式

输入的第一行包含一个整数 NN1N201\le N\le 20)。以下 NN 行每行包含一个长度不小于 44 且不超过 100100 的字符串,表示一个栅栏的路径。

输出格式

NN 条输入的栅栏路径的每一条,输出一行,为 CW(clockwise,顺时针)或 CCW(counterclockwise,逆时针)。

2
NESW
WSSSEENWNEESSENNNNWWWS
CW
CCW

提示

样例解释 1

以下为这两条栅栏路径,用 @ 表示起始位置:

*>*
^ v
@<*
  *<*<*<*
  v     ^
*<@     *
v       ^
* *>*>* *
v ^   v ^
* *<* * *
v   ^ v ^
*>*>* *>*