Description
有一个 \(n\times m\) 的停车场，每个坐标有一辆车或一块空地，每辆车面朝一个方向，用 N（北）、E（东）、S（南）、W（西），代表面朝的方向（上北下南左西右东），否则用 .表示空地。
每辆车能被移开，当且仅当它面向的这条线上没有一辆车或挡着的车都已被移开，求一个移动方案使得所有车都能被依次移开，每次移动一辆车且必须要移开（即不能只移一半），输出这辆车的坐标（左上角坐标为 \((0,0)\)）。
题目保证有解。
Solution
很容易想到拓扑建图，因为有约束关系，约束的车向被约束的车连一条边，一条车能移开当且仅当它的入度为零，关键在于建图。
如果一辆车向所有在它前方的车连一条边，时空复杂度都是 \(O(n^3)\)，跑不过的。
所以要优化建图。对于一辆车，如果它前方有一个同一方向的车，那就不用向这辆车前面的车连边了，因为如果这辆车能移开，那么前面所有的车都能移开。然后两辆中间的都连。乍一看，感觉没怎么优化，但实际上已经优化到 \(O(2n^2)\) 了。
对于一辆车它最多只会建两条边：
- 同方向的车，只连向在它后面的第一辆
- 不同方向的车，只会连一辆
如：
..N.
ESEE
..W.
..N.
\((1,2)\) 的车只会连向 \((1,0)\) 和 \((3,2)\)，对于第一种好理解，第二种因为保证有解，所以不会同时存在两种对立方向 S和 N都对向这个点（都不对向是有可能的，但没约束关系），同时对于第三列的 W（与当前车的对立方向）也是没有约束关系的，所以只会对第三列第二行以后的第一个 N（或 S，示例为 N）连边。
Code
#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int n,m;
int tot,head[4000040];
int a[2020][2020];
int in[4000040];
struct node{
int x,y,tp;
}b[4000040];
struct edge{
int to,next;
}e[8000080];
void add(int x,int y){
in[y]++;
e[++tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=1;j<=m;j++){
if(s[j-1]!='.'){
cnt++;
a[i][j]=cnt,b[cnt].x=i,b[cnt].y=j;
if(s[j-1]=='N') b[cnt].tp=1;
if(s[j-1]=='S') b[cnt].tp=2;
if(s[j-1]=='E') b[cnt].tp=3;
if(s[j-1]=='W') b[cnt].tp=4;
}
}
}
for(int i=1;i<=cnt;i++){
if(b[i].tp==1){ //对于四种情况分类建图
bool f1=0;
for(int j=b[i].x-1;j>=1;j--){
if(b[a[j][b[i].y]].tp==1){
if(!f1){
add(a[j][b[i].y],i);
f1=1;
break;
}
}else if(b[a[j][b[i].y]].tp!=0){
add(a[j][b[i].y],i);
}
}
}
if(b[i].tp==2){
bool f1=0;
for(int j=b[i].x+1;j<=n;j++){
if(b[a[j][b[i].y]].tp==2){
if(!f1){
add(a[j][b[i].y],i);
f1=1;
break;
}
}else if(b[a[j][b[i].y]].tp!=0){
add(a[j][b[i].y],i);
}
}
}
if(b[i].tp==3){
bool f1=0;
for(int j=b[i].y+1;j<=m;j++){
if(b[a[b[i].x][j]].tp==3){
if(!f1){
add(a[b[i].x][j],i);
f1=1;
break;
}
}else if(b[a[b[i].x][j]].tp!=0){
add(a[b[i].x][j],i);
}
}
}
if(b[i].tp==4){
bool f1=0;
for(int j=b[i].y-1;j>=1;j--){
if(b[a[b[i].x][j]].tp==4){
if(!f1){
add(a[b[i].x][j],i);
f1=1;
break;
}
}else if(b[a[b[i].x][j]].tp!=0){
add(a[b[i].x][j],i);
}
}
}
}
for(int i=1;i<=cnt;i++){
if(in[i]==0) q.push(i);
}
while(q.size()){
int x=q.front();
q.pop();
cout<<"("<<b[x].x-1<<","<<b[x].y-1<<")"<<endl;
for(int i=head[x];i;i=e[i].next){ //topo sort
int y=e[i].to;
in[y]--;
if(in[y]==0){
q.push(y);
}
}
}
return 0;
}