欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF243C Colorado Potato Beetle

程序员文章站 2022-04-15 23:41:11
一、题目...

一、题目

点此看题

二、解法

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

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

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

#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

相关标签: 搜索