注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2541][Ctsc2000]冰原探险  

2015-06-20 16:18:12|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2541: [Ctsc2000]冰原探险

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 9
[Submit][Status][Discuss]

Description

传说中,南极有一片广阔的冰原,在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相等的方格。在这个冰原上有N个大小不等的矩形冰山,这些巨大的冰山有着和南极一样古老的历史,每个矩形冰山至少占据一个方格,且其必定完整地占据方格。冰山和冰山之间不会重叠,也不会有边或点相连。以下两种情况均是不可能出现的:

ACM探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料,在这个冰原上一个大小为一格的深洞中,藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可移动的小冰块。显然,在南极是不可能有这样小的独立冰块的,所以这块冰块也一定是史前文明的产物。他们在想办法把这个冰块推到洞里去,这样就可以打开一条通往冰原底部的通道,发掘史前文明的秘密。冰块的起始位置与深洞的位置均不和任何冰山相邻。这个冰原上的冰面和冰山都是完全光滑的,轻轻的推动冰块就可以使这个冰块向前滑行,直到撞到一座冰山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域,也可以从两座冰山之间穿过(见下图)。冰块只能沿网格方向推动。

请你帮助他们以最少的推动次数将冰块推入深洞中。

Input

    输入文件第一行为冰山的个数N (1<=N<=4000),第二行为冰块开始所在的方格坐标X1,Y1,第三行为深洞所在的方格坐标X2,Y2,以下N行每行有四个数,分别是每个冰山所占的格子左上角和右下角坐标Xi1,Yi1,Xi2,Yi2

Output

    输出文件仅包含一个整数,为最少推动冰块的次数。如果无法将冰块推入深洞中,则输出0

Sample Input

2 1 1 5 5 1 3 3 3 6 2 8 4

Sample Output

3

Solution

对于一个矩形,我们可以把它离散化成4个点(4条边),因为碰到这些边之后我们接下来的一步只有向上或者向下(向左或者向右)2种操作了,所以落在边上的哪个点都是无差的
时间复杂度O(n^2)
边spfa边建图就好了没必要一开始把图建完因为不是满的。

Code

/**************************************************************
    Problem: 2541
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:152 ms
    Memory:1956 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 4010
int n,sx,sy,tx,ty,i,x0[N],y0[N],x1[N],y1[N],l=1,r,vis[N<<2],min,max,oo=1<<30,i0,i1;
struct Q{int op,x,y,d;}q[1<<16];
int main(){
    scanf("%d%d%d%d%d",&n,&sx,&sy,&tx,&ty);
    for(i=1;i<=n;i++)scanf("%d%d%d%d",x0+i,y0+i,x1+i,y1+i);
    for(q[++r]=(Q){0,sx,sy,0},q[++r]=(Q){1,sx,sy,0};l<=r;l++)
    if(q[l].op==0){
        for(i0=i1=0,max=-oo,min=oo,i=1;i<=n;i++)//left&&right
        if(y0[i]<=q[l].y&&q[l].y<=y1[i]){
            if(x1[i]<q[l].x&&max<x1[i])max=x1[i0=i];
            if(q[l].x<x0[i]&&min>x0[i])min=x0[i1=i];
        }
        if(i0&&!vis[i0<<2|1])vis[i0<<2|1]=1,q[++r]=(Q){1,x1[i0]+1,q[l].y,q[l].d+1};
        if(i1&&!vis[i1<<2|3])vis[i1<<2|3]=1,q[++r]=(Q){1,x0[i1]-1,q[l].y,q[l].d+1};
        if(q[l].y==ty&&max<=tx&&tx<=min)return printf("%d\n",q[l].d+1),0;
    }
    else{
        for(i0=i1=0,max=-oo,min=oo,i=1;i<=n;i++)//up&&down
        if(x0[i]<=q[l].x&&q[l].x<=x1[i]){
            if(y1[i]<q[l].y&&max<y1[i])max=y1[i0=i];
            if(q[l].y<y0[i]&&min>y0[i])min=y0[i1=i];
        }
        if(i0&&!vis[i0<<2  ])vis[i0<<2  ]=1,q[++r]=(Q){0,q[l].x,y1[i0]+1,q[l].d+1};
        if(i1&&!vis[i1<<2|2])vis[i1<<2|2]=1,q[++r]=(Q){0,q[l].x,y0[i1]-1,q[l].d+1};
        if(q[l].x==tx&&max<=ty&&ty<=min)return printf("%d\n",q[l].d+1),0;
    }
    puts("0");
}

  评论这张
 
阅读(82)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018