题解 CF243C 【Colorado Potato Beetle】
frankchenfu
2018-03-17 12:13:41
因为这片土地的大小是$10^{10}+1$的，输入数据最大只有$10^3\times 10^6 = 10^9$，所以我们可以把这个土地看做是无限大的。
然后题目要求的是线段围成的封闭路径，所以我们可以考虑直接搜索。可是，范围高达$10^{20}$，不能搜索。因为题目中只有$10^3$条线段，所以我们可以考虑将其离散化。这样，我们就可以很愉快的在$2000\times 2000$的范围内进行`BFS`染色了，并且空间也可以接受。我们从$(0,0)$（这个是取不到的点）开始染色，没有被染色的部分就是封闭的。
在实现上，我们可以在最外面加上四条“边框”，这样就可以搜索了。代码如下：
```cpp
#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;
}
```