CF243C Colorado Potato Beetle

一、题目

点此看题

二、解法

可以离散化之后搜索，离散化的目的是把一个较大的矩形缩小成一个格子，保证复杂度在 O ( 200 0 2 ) O(2000^2) O(20002)

先排序，离散的套路是把 x x x轴和 y y y轴分别处理，相邻两者之间的长度离散成 1 1 1，但还有一个问题，由于走过的点就算没有围成闭合图形也不能经过，所以需要在每一个点处多开一段长度为 1 1 1的段， x , y x,y x,y两两配对就围成了矩形，跑 b f s bfs bfs即可。

细节太多辣，贴个有注释的代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 2005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9'){if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,tx[M],ty[M],p[M][2];//tx,ty用来离散化，p存端点 
int totx,toty,px[M],py[M],lenx[M],leny[M];//x轴处的数量，y轴处的数量，xy用来算编号的数组，点离散后的长度 
int sx,sy,dx[4]={-1,1},dy[4]={0,0,-1,1};
bool vis[M][M],mark[M][M];long long ans;
struct node
{
int x,y;
};
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
int x,k;char s[5];
scanf("%s",s);x=read();
if(s[0]=='U') k=0;
if(s[0]=='D') k=1;
if(s[0]=='L') k=2;
if(s[0]=='R') k=3;
tx[i]=sx;ty[i]=sy;
sx+=dx[k]*x;sy+=dy[k]*x;
p[i][0]=sx;p[i][1]=sy;
}
tx[n+1]=sx;ty[n+1]=sy;
sort(tx+1,tx+2+n);
sort(ty+1,ty+2+n);
tx[0]=unique(tx+1,tx+2+n)-tx-1;//去重 
totx=toty=1;//给(1,1)蝗虫出发的点腾个位置 
for(int i=1;i<=tx[0];i++)
{
px[i+1]=px[i];
lenx[++totx]=1;//建一段长度为1 
if(i<tx[0] && tx[i]+1==tx[i+1]) px[i+1]++;//这个端点前有多少次没有二次设置 
else lenx[++totx]=tx[i+1]-tx[i]-1;
}
ty[0]=unique(ty+1,ty+2+n)-ty-1;
for(int i=1;i<=ty[0];i++)
{
py[i+1]=py[i];
leny[++toty]=1;
if(i<ty[0] && ty[i]+1==ty[i+1]) py[i+1]++;
else leny[++toty]=ty[i+1]-ty[i]-1;
}
int x=0,y=0,lx=0,ly=0;
for(int i=0;i<=n;i++,lx=x,ly=y)//“墙”的处理 
{
x=lower_bound(tx+1,tx+1+tx[0],p[i][0])-tx;
y=lower_bound(ty+1,ty+1+ty[0],p[i][1])-ty;
x=x*2-px[x];y=y*2-py[y];//算编号 
if(i)
{
if(lx==x)//看走的方向 
for(int j=min(ly,y);j<=max(ly,y);j++)
mark[x][j]=1;
else
for(int j=min(lx,x);j<=max(lx,x);j++)
mark[j][y]=1;
}
}
queue<node> q;
q.push(node{1,1});
vis[1][1]=1;
while(!q.empty())//暴力bfs 
{
node t=q.front();q.pop();
for(int i=0;i<4;i++)
{
int tx=t.x+dx[i],ty=t.y+dy[i];
if(tx>=1 && tx<=totx && ty>=1 && ty<=toty && !mark[tx][ty] && !vis[tx][ty])
{
vis[tx][ty]=1;
q.push(node{tx,ty});
}
}
}
for(int i=1;i<=totx;i++)
for(int j=1;j<=toty;j++)
if(!vis[i][j])
ans+=1ll*lenx[i]*leny[j];
printf("%lld\n",ans);
}

本文地址：https://blog.csdn.net/C202044zxy/article/details/107620848