frankchenfu 的博客

frankchenfu 的博客

题解 CF243C 【Colorado Potato Beetle】

posted on 2018-03-17 12:13:41 | under 题解 |

因为这片土地的大小是$10^{10}+1$的,输入数据最大只有$10^3\times 10^6 = 10^9$,所以我们可以把这个土地看做是无限大的。

然后题目要求的是线段围成的封闭路径,所以我们可以考虑直接搜索。可是,范围高达$10^{20}$,不能搜索。因为题目中只有$10^3$条线段,所以我们可以考虑将其离散化。这样,我们就可以很愉快的在$2000\times 2000$的范围内进行BFS染色了,并且空间也可以接受。我们从$(0,0)$(这个是取不到的点)开始染色,没有被染色的部分就是封闭的。

在实现上,我们可以在最外面加上四条“边框”,这样就可以搜索了。代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN=2010;
const ll INF=1ll<<47;
const ll way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};  

struct rect{
    ll p1,q1,p2,q2;
}rec[MAXN];

int n,tot=0;
int vis[MAXN][MAXN];
int lst[2],now[2];
map<ll,int>xpos,ypos;
vector<ll>x,y;
queue<pair<ll,ll> >q;

inline int max(int x,int y){
    return x>y?x:y;
}
inline int min(int x,int y){
    return x<y?x:y;
}

void adde(int ord){
    char opt[3];int val;
    scanf("%s%d",opt,&val);
    switch(opt[0]){
        case 'U':{
            now[0]=lst[0]-val;
            now[1]=lst[1];
            break;
        }
        case 'D':{
            now[0]=lst[0]+val;
            now[1]=lst[1];
            break;
        }
        case 'L':{
            now[0]=lst[0];
            now[1]=lst[1]-val;
            break;
        }
        case 'R':{
            now[0]=lst[0];
            now[1]=lst[1]+val;
            break;
        }
        default:{
            puts("Error");
            return;
        }
    }
    x.push_back(min(lst[0],now[0]));x.push_back(max(lst[0],now[0])+1);
    y.push_back(min(lst[1],now[1]));y.push_back(max(lst[1],now[1])+1);
    rec[ord]=(rect){min(lst[0],now[0]),min(lst[1],now[1]),max(lst[0],now[0])+1,max(lst[1],now[1])+1};
    lst[0]=now[0];lst[1]=now[1];
}

int match(vector<ll>v,ll num){  
    return find(v.begin(),v.end(),num)-v.begin();  
}  

int main(){
    x.push_back(-INF);x.push_back(INF);
    y.push_back(-INF);y.push_back(INF);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        adde(i);
    sort(x.begin(),x.end());sort(y.begin(),y.end());
    x.resize(unique(x.begin(),x.end())-x.begin());
    y.resize(unique(y.begin(),y.end())-y.begin());

    for(int i=0;i<n;i++){  
        lst[0]=match(x,rec[i].p1);now[0]=match(x,rec[i].p2)-1;  
        lst[1]=match(y,rec[i].q1);now[1]=match(y,rec[i].q2)-1;  
        for(int j=lst[0];j<=now[0];j++)  
            for(int k=lst[1];k<=now[1];k++)  
                vis[j][k]=1;  
    }  
    q.push(make_pair(0,0));vis[0][0]=2;
    while(!q.empty()){
        pair<ll,ll>u,v;
        u=q.front();q.pop();
        for(int i=0;i<4;i++){
            v=u;
            v.first+=way[i][0];v.second+=way[i][1];
            if(v.first>=0&&v.first<x.size()&&v.second>=0&&v.second<y.size()&&vis[v.first][v.second]==0){  
                vis[v.first][v.second]=2;  
                q.push(v);  
            }
        }
    }
    ll ans=0;  
    for(int i=0;i<x.size()-1;i++)  
        for(int j=0;j<y.size()-1;j++)  
            if(vis[i][j]!=2)  
                ans+=(x[i+1]-x[i])*(ll)(y[j+1]-y[j]);  
    printf("%lld\n",ans);  
    return 0;
}