#P5474. [CCO2015] 冰上车

[CCO2015] 冰上车

题目描述

本题译自 CCO 2015 Day2 T1「Cars on Ice

在圣诞夜守卫银行是一件非常无聊的事情。这就是 Barry 想要去停车场附近溜冰的原因。然而因为其他守卫把车停在了那里,停车场并不是空的。所以 Barry 决定把他们的车推出停车场。他注意到那些停着的车面对的方向是东南西北之一。因为停车场结冰了,所以推一辆车将会使得他滑行直至离开停车场或撞上其他的车。这些车只能朝他们面向的方向推。为了不撞车,Barry 找你帮忙,让你帮他计算出将车推出停车场的顺序,以便他清空停车场。

输入格式

第一行包括两个整数 N,MN,M,表示停车场的行列数。
接下来 NN 行每行 MM 个字符,描述一个停车场。其中 . 代表这是一个空的车位,而 N, E, W, S 表示一辆车,分别表示这辆车面朝北、南、东、西。

输出格式

输出在不发生撞车的情况下将车推出的顺序,每辆车按格式 (r,c)(r,c) 输出,其中 (r,c)(r,c) 是车在停车场中的坐标,(0,0)(0,0) 为左上角,(N1,M1)(N-1,M-1) 为右下角。
保证至少有一个有效解,如果有多个解,输出任意一个。

5 5
.....
.E.S.
.....
.....
.N.E.
(4,3)
(1,3)
(1,1)
(4,1)
4 3
...
.N.
.S.
...
(1,1)
(2,1)

提示

样例解释 1

唯一一辆在开始时没有被其他车挡住的是在 (4,3)(4,3) 的车,当这架车被推到停车场右边后,在它上面的车(在 (1,3)(1,3) 的车)可以被推出,然后是在 (1,1)(1,1) 的车,最后是在 (4,1)(4,1) 的车,停车场得以清空。

样例解释 2

两辆车都可以作为第一个被推出停车场的车,所以样例输出 2 是正确的,同时顺序与其相反的输出也是正确的。

数据范围

对于 70%70\% 的数据,1N,M1001\le N,M \le 100

对于 100%100\% 的数据,1N,M20001\le N,M \le 2000