#include<bits/stdc++.h>
#define N 4000001
#define M 2001
using namespace std;
struct edge{
	int u,v;
};
vector<edge>e[N];
int n,m,t=1;
struct car{
	short x,y;
	int id;
	char fx;
}line[M][M],column[M][M];
car* ca=(car*)malloc(sizeof(car)*N);
int judge(char x){
	return (x>='A'&&x<='Z');
}
int cmpl(car a,car b){
	return a.y<b.y;
}
int cmpc(car a,car b){
	return a.x<b.x;
}
short ltop[M],ctop[M];
bool lsorted[M],csorted[M];
short in[N];
queue<int>top,ans;
int find1(int l,int r,int li,int k){
	while(l<=r){
		int mid=(l+r)>>1;
		if(line[li][mid].id==k){
			return mid;
		}
		else if(line[li][mid].id<k){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
int find2(int l,int r,int co,int k){
	while(l<=r){
		int mid=(l+r)>>1;
		if(column[co][mid].id==k){
			return mid;
		}
		else if(column[co][mid].id<k){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
void topo(int n){
	for(int i=1;i<=n;i++){
		if(!in[i]){
			top.push(i);
		}
	}
	while(!top.empty()){
		int u=top.front();
		top.pop();
		ans.push(u);
		for(int i=0;i<(int)e[u].size();i++){
			int v=e[u][i].v;
			if(!(--in[v])){
				top.push(v);
			}
		}
	} 
	return;
}
int main(){
	cin>>n>>m;
	for(short i=0;i<n;i++){
		for(short j=0;j<m;j++){
		    char c;
			cin>>c;
			if(judge(c)){
				ca[t]=(car){i,j,t,c};
				line[i][++ltop[i]]=ca[t];
				column[j][++ctop[j]]=ca[t];
				t++;
			}
		}
	}
	for(int i=1;i<t;i++){
		int li=ca[i].x,co=ca[i].y;
		if(ca[i].fx=='E'){
			if(!lsorted[li]){
				sort(line[li]+1,line[li]+1+ltop[li],cmpl);
				lsorted[li]=1;
			}
			int l=1,r=ltop[li];
			int fx=find1(l,r,li,i);
			for(short j=fx+1;j<=ltop[li];j++){
				int u=line[li][j].id;
				e[u].push_back((edge){u,i});
				in[i]++;
			}
		}
		else if(ca[i].fx=='W'){
			if(!lsorted[li]){
				sort(line[li]+1,line[li]+1+ltop[li],cmpl);
				lsorted[li]=1;
			}
			int l=1,r=ltop[li];
			int fx=find1(l,r,li,i);
			for(short j=1;j<fx;j++){
				int u=line[li][j].id;
				e[u].push_back((edge){u,i});
				in[i]++;
			}
		}
		else if(ca[i].fx=='S'){
			if(!csorted[co]){
				sort(column[co]+1,column[co]+1+ctop[co],cmpc);
				csorted[co]=1;
			}
			int l=1,r=ctop[co];
			int fy=find2(l,r,co,i);
			for(short j=fy+1;j<=ctop[co];j++){
				int u=column[co][j].id;
				e[u].push_back((edge){u,i});
				in[i]++;
			}
		}
		else if(ca[i].fx=='N'){
			if(!csorted[co]){
				sort(column[co]+1,column[co]+1+ctop[co],cmpc);
				csorted[co]=1;
			}
			int l=1,r=ctop[co];
			int fy=find2(l,r,co,i);
			for(short j=1;j<fy;j++){
				int u=column[co][j].id;
				e[u].push_back((edge){u,i});
				in[i]++;
			}
		}
	}
	topo(t-1);
	while(!ans.empty()){
		int p=ans.front();
		ans.pop();
		cout<<'('<<ca[p].x<<','<<ca[p].y<<')'<<endl;
	}
	return 0;
} 

思路：首先把所有阻碍第 $i$ 辆车的车与车辆 $i$ 连边，然后拓扑排序求解