2795 「CCO 2015」冰上车

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

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

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

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

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

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

对于 $70\%$ 的数据，$1\le N,M \le 100$；

对于 $100\%$ 的数据，$1\le N,M \le 2000$。