P14273 [ROI 2014 Day1] 鲁滨逊与鳄鱼题解

1.题意简述

给一个网格，求最多消掉多少个格子。我们称一个格子能被消除，当且仅当它不为空且它对应方向的格子均为空。把一个格子消掉后，该格子变为空。

具体方向如下：

• N —— 向北；
• S —— 向南；
• E —— 向东；
• W —— 向西。

2.思路1

很明显，如果暴力枚举每个格子能否消除，复杂度无法接受，所以我们要换一个思路。

考虑建图跑拓扑排序。

对于一个不为空的点，将它和其对应方向的 所有不为空的点 连 有向边，让别的点指向它，并记录入度，如果 入度为零 就压入队列进行拓扑排序，时间的瓶颈在于建图，大概是 $O(n^2m)$ 的。

代码如下，建图的时候比较麻烦，码风 duliu，将就着看吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2010;
int n,m,cnt,in[N][N];
char c[N][N];
vector<pair<int,int> > e[N][N];
void Do(char ch,int x,int y){
    if(ch=='N') for(int i=x-1;i;--i) if(c[i][y]!='.') e[i][y].push_back({x,y}),in[x][y]++;
    if(ch=='S') for(int i=x+1;i<=n;++i) if(c[i][y]!='.') e[i][y].push_back({x,y}),in[x][y]++;
    if(ch=='W') for(int i=y-1;i;--i) if(c[x][i]!='.') e[x][i].push_back({x,y}),in[x][y]++;
    if(ch=='E') for(int i=y+1;i<=m;++i) if(c[x][i]!='.') e[x][i].push_back({x,y}),in[x][y]++;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    queue<pair<int,int> > q;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>c[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            Do(c[i][j],i,j);
            if(!in[i][j] && c[i][j]!='.') q.push({i,j});
        }
    }
    while(!q.empty()){
        cnt++;
        int x=q.front().first,y=q.front().second;
        q.pop();
        for(auto v:e[x][y]){
            int tx=v.first,ty=v.second;
            in[tx][ty]--;
            if(!in[tx][ty]) q.push({tx,ty});
        }
    }
    cout<<cnt;
    return 0;
}

但是你发现 Subtask #2 和 Subtask #3 全部 MLE！！！所以要考虑优化空间。

3.优化

1.变量

去掉 #define int long long，不知道当时为什么要写。

2.依旧变量

把除了 cnt 的所有变量改成 short。

3.优化建图

每次连边连到和当前点方向相同就停止。

4.AC 代码

#include<bits/stdc++.h>
using namespace std;
const short N = 2010;
short n,m,in[N][N];
int cnt;
char c[N][N];
vector<pair<short,short>> e[N][N];
queue<pair<short,short>> q;
void Do(char ch,short x,short y){
    if(ch=='N' && x!=1) {short i=x;do{i--;if(c[i][y]!='.') e[i][y].push_back({x,y}),in[x][y]++;}while(i>1&&c[i][y]!=ch);}
    if(ch=='S' && x!=n) {short i=x;do{i++;if(c[i][y]!='.') e[i][y].push_back({x,y}),in[x][y]++;}while(i<n&&c[i][y]!=ch);}
    if(ch=='W' && y!=1) {short i=y;do{i--;if(c[x][i]!='.') e[x][i].push_back({x,y}),in[x][y]++;}while(i>1&&c[x][i]!=ch);}
    if(ch=='E' && y!=m) {short i=y;do{i++;if(c[x][i]!='.') e[x][i].push_back({x,y}),in[x][y]++;}while(i<m&&c[x][i]!=ch);}
    if(!in[x][y]) q.push({x,y});
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    for(short i=1;i<=n;++i) for(short j=1;j<=m;++j) cin>>c[i][j];
    for(short i=1;i<=n;++i) for(short j=1;j<=m;++j) if(c[i][j]!='.') Do(c[i][j],i,j);
    while(!q.empty()){
        cnt++;
        short x=q.front().first,y=q.front().second,tx,ty;
        q.pop();
        for(auto v:e[x][y]){
            tx=v.first,ty=v.second,in[tx][ty]--;
            if(!in[tx][ty]) q.push({tx,ty});
        }
    }
    cout<<cnt;
    return 0;
}