解题思路
若车 \(A\) 限制车 \(B\) 离开，则 \(A\) 先于 \(B\) 离开，所有的限制条件构成了一个拓扑结构。
若 \(A\) 限制 \(B\)，\(A\) 向 \(B\) 连边，最终可以使用拓扑排序求解。
而查找每个车辆的约束车辆时间复杂度为 \(\mathcal{O}(n\times m\times(n+m))\)，预计得分 \(70\text{pts}\)。
对于两个同一行或列，若有两辆方向相同的车，则对于其他约束其中一辆车的车，必定也约束另一辆车，从而只需建一条边就好了。
所以每辆车最多限制其两侧的两辆车。总时间复杂度为 \(\mathcal{O}(2\times n\times m+n+m)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, m;
char c[N][N];
vector<int> e[N * N];
int f[N * N], tot, d[N * N];
pair<int, int> rf[N * N];
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> c[i];
for(int j = 0; j < m; j++) {
if(c[i][j] != '.') {
f[i * n + j] = ++tot;
rf[tot] = {i, j};
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(c[i][j] == 'N') { // 向上
for(int k = i - 1; k >= 0; k--) {
if(c[k][j] != '.') {
e[f[k * n + j]].push_back(f[i * n + j]);
++d[f[i * n + j]];
if(c[k][j] == c[i][j]) {
break;
}
}
}
} else if(c[i][j] == 'E') { // 向右
for(int k = j + 1; k < m; k++) {
if(c[i][k] != '.') {
e[f[i * n + k]].push_back(f[i * n + j]);
++d[f[i * n + j]];
if(c[i][k] == c[i][j]) {
break;
}
}
}
} else if(c[i][j] == 'W') { // 向左
for(int k = j - 1; k >= 0; k--) {
if(c[i][k] != '.') {
e[f[i * n + k]].push_back(f[i * n + j]);
++d[f[i * n + j]];
if(c[i][k] == c[i][j]) {
break;
}
}
}
} else if(c[i][j] == 'S') { // 向下
for(int k = i + 1; k < n; k++) {
if(c[k][j] != '.') {
e[f[k * n + j]].push_back(f[i * n + j]);
++d[f[i * n + j]];
if(c[k][j] == c[i][j]) {
break;
}
}
}
}
}
}
queue<int> q;
for(int i = 1; i <= tot; i++) {
if(!d[i]) {
q.push(i);
}
}
while(!q.empty()) {
int tmp = q.front();
q.pop();
printf("(%d,%d)\n", rf[tmp].first, rf[tmp].second);
for(int i : e[tmp]) {
--d[i];
if(!d[i]) {
q.push(i);
}
}
}
return 0;
}