题解

13 条题解

  • 1
    @ 2016-10-30 16:02:29

    这道冰原探险就是个BFS,刚开始做的时候没有考虑到冰川是4面(好像有点傻。。),然后判断只要到过这个冰川就不能在到达了,,结果只得了60分(能得这么多已经很开心了。),,后来一想,应该是**冰川的一侧不能到达两遍!!**于是改了改就A了。
    代码如下:

    /*
    My convictions will not falter.--Poppy
    */
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define N 50000
    using namespace std;
    int tail=0,head=0,u,n,b1,b2,e1,e2;
    int qx[N],qy[N],qd[N],qt[N],lx[N],ly[N],rx[N],ry[N],pd[N][5];
    /*qx,qy,qd,qt都是队列,qd是当前的小冰块滑动的方向(1代表下面有冰川将要左右滑,-1反之),
    qx,qy就是坐标啦,qt是到达当前状态所需的步数,pd就是判断当前状态是否已经到达过,
    每一个冰川四种状态*/
    int judge(int x,int y,int d)
    {
    int m1=2147483647,mi1=-1,m2=-2147483647,mi2=-1,i;
    if(d==1)//左右滑
    {
    for(i=1;i<=n;i++)
    {
    if(ly[i]<m1&&ly[i]>y&&lx[i]<=x&&rx[i]>=x)//如果向右滑能碰到的冰川可以挡住冰块
    m1=ly[i],mi1=i;
    if(ry[i]>m2&&ry[i]<y&&lx[i]<=x&&rx[i]>=x)//向左
    m2=ry[i],mi2=i;
    }
    if(e1==x&&e2<m1&&e2>m2) return 1;
    if(mi1>0&&!pd[mi1][1])
    qx[++head]=x,qy[head]=m1-1,qd[head]=-d,qt[head]=qt[u]+1,pd[mi1][1]=1;
    //qd[head]=-d,这次左右滑能停下,下次必定上下滑,因为如果再左右滑,又回到了原来的状态,必定不是最优
    if(mi2>0&&!pd[mi2][3])
    qx[++head]=x,qy[head]=m2+1,qd[head]=-d,qt[head]=qt[u]+1,pd[mi2][3]=1;
    }
    if(d==-1)//上下滑
    {
    for(i=1;i<=n;i++)
    {
    if(lx[i]<m1&&lx[i]>x&&ly[i]<=y&&ry[i]>=y)//向下
    m1=lx[i],mi1=i;
    if(rx[i]>m2&&rx[i]<x&&ly[i]<=y&&ry[i]>=y)//向上
    m2=rx[i],mi2=i;
    }
    if(e2==y&&e1<m1&&e1>m2) return 1;
    if(mi1>0&&!pd[mi1][4])
    qx[++head]=m1-1,qy[head]=y,qd[head]=-d,qt[head]=qt[u]+1,pd[mi1][4]=1;
    if(mi2>0&&!pd[mi2][2])
    qx[++head]=m2+1,qy[head]=y,qd[head]=-d,qt[head]=qt[u]+1,pd[mi2][2]=1;
    }
    return 0;
    }
    int main()
    {
    scanf("%d",&n);
    scanf("%d%d",&b1,&b2);
    scanf("%d%d",&e1,&e2);
    int i;
    for(i=1;i<=n;i++)
    scanf("%d%d%d%d",&lx[i],&ly[i],&rx[i],&ry[i]);
    tail=0,head=0;
    if(judge(b1,b2,1))
    {
    printf("%d",qt[u]+1);
    return 0;
    }
    if(judge(b1,b2,-1))
    {
    printf("%d",qt[u]+1);
    return 0;
    }//一开始的冰块可以向4个方向滑
    while(tail<head)
    {
    tail++;
    u=tail;
    if(judge(qx[u],qy[u],qd[u]))
    {
    printf("%d",qt[u]+1);
    return 0;
    }
    }
    printf("0");
    return 0;
    }

  • 0
    @ 2017-07-09 21:14:00

    裸Bfs+Hashmap判重+上一次上下滑这一次只能左右滑剪枝
    代码又臭又长
    注意地图坐标可能为负

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #include<map>
    using namespace std;
    inline const int Get_Int() {
        int num=0,bj=1;
        char x=getchar();
        while(x<'0'||x>'9') {
            if(x=='-')bj=-1;
            x=getchar();
        }
        while(x>='0'&&x<='9') {
            num=num*10+x-'0';
            x=getchar();
        }
        return num*bj;
    }
    struct Point {
        int x,y,time,last;
    } Start,End,LeftUp[5005],RightDown[5005];
    map<int,map<int,int> >vst;
    int n;
    bool Judge(int x,int y,int direction,int& Nextx,int& Nexty) {
        if(direction==1) { //右滑
            Nextx=0x7fffffff/2;
            for(int i=1; i<=n; i++)
                if(x<LeftUp[i].x-1&&y>=LeftUp[i].y&&y<=RightDown[i].y) {
                    Nextx=min(Nextx,LeftUp[i].x-1);
                    Nexty=y;
                }
            if(x<End.x&&y==End.y&&(Nextx>=End.x||!Nextx)) {
                Nextx=End.x;
                Nexty=End.y;
                return true;
            }
            if(Nextx!=0x7fffffff/2)return true;
        } else if(direction==2) { //左滑 
            Nextx=-0x7fffffff/2;
            for(int i=1; i<=n; i++)
                if(x>RightDown[i].x+1&&y>=LeftUp[i].y&&y<=RightDown[i].y) {
                    Nextx=max(Nextx,RightDown[i].x+1);
                    Nexty=y;
                }
            if(x>End.x&&y==End.y&&(Nextx<=End.x||!Nextx)) {
                Nextx=End.x;
                Nexty=End.y;
                return true;
            }
            if(Nextx!=-0x7fffffff/2)return true;
        } else if(direction==3) { //上滑 
            Nexty=-0x7fffffff/2;
            for(int i=1; i<=n; i++)
                if(y>RightDown[i].y+1&&x>=LeftUp[i].x&&x<=RightDown[i].x) {
                    Nextx=x;
                    Nexty=max(Nexty,RightDown[i].y+1);
                }
            if(x==End.x&&y>End.y&&(Nexty<=End.y||!Nexty)) {
                Nextx=End.x;
                Nexty=End.y;
                return true;
            }
            if(Nexty!=-0x7fffffff/2)return true;
        } else { //下滑 
            Nexty=0x7fffffff/2;
            for(int i=1; i<=n; i++)
                if(y<LeftUp[i].y-1&&x>=LeftUp[i].x&&x<=RightDown[i].x) {
                    Nextx=x;
                    Nexty=min(Nexty,LeftUp[i].y-1);
                }
            if(x==End.x&&y<End.y&&(Nexty>=End.y||!Nexty)) {
                Nextx=End.x;
                Nexty=End.y;
                return true;
            }
            if(Nexty!=0x7fffffff/2)return true;
        }
        return false;
    }
    void Bfs() {
        queue<Point>Q;
        Q.push(Start);
        vst[Start.x][Start.y]=1;
        while(!Q.empty()) {
            Point Now=Q.front();
            Q.pop();
            if(Now.x==End.x&&Now.y==End.y) {
                printf("%d\n",Now.time);
                return;
            }
            int Nextx=0,Nexty=0,i=1,Max=4;
            if(Now.last==1||Now.last==2)i=3;
            else if(Now.last==3||Now.last==4)Max=2;
            for(; i<=Max; i++)
                if(Judge(Now.x,Now.y,i,Nextx,Nexty)&&(!vst.count(Nextx)||!vst[Nextx].count(Nexty))) {
                    Q.push((Point) {
                        Nextx,Nexty,Now.time+1,i
                    });
                    vst[Nextx][Nexty]=1;
                }
        }
        puts("0");
    }
    int main() {
        n=Get_Int();
        Start.x=Get_Int(),Start.y=Get_Int();
        End.x=Get_Int(),End.y=Get_Int();
        for(int i=1; i<=n; i++) {
            LeftUp[i].x=Get_Int();
            LeftUp[i].y=Get_Int();
            RightDown[i].x=Get_Int();
            RightDown[i].y=Get_Int();
        }
        Bfs();
        return 0;
    }
    
  • 0
    @ 2009-08-05 15:36:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 41ms

    ├ 测试数据 09:答案正确... 322ms

    ├ 测试数据 10:答案正确... 228ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:591ms

    Flag   Accepted

    题号   P1366

    类型(?)   图结构

    通过   30人

    提交   100次

    通过率   30%

    难度   4

    just 宽搜

  • 0
    @ 2009-05-29 12:42:48

    冰川底下有地下室??

  • 0
    @ 2009-04-06 14:19:36

    太晕了,把方向写错了,只怪我太懒,太粗心了.

    这题其实很简单的bfs,只是判重不同一点,但要注意坐标有负数,不过也没什么影响!!!!!

  • 0
    @ 2009-01-31 15:18:10

    太激动啦,感谢宇智波带狗提供数据

  • 0
    @ 2008-10-22 18:47:56

    1、我把终点当作第0个障碍,结果判断的时候写成了>=1

    2、必须判断是否直接到达终点,而不能只要求到达终点附近的一格的地方

    3、可能出现死圈,所以需要判重

    4、我用Hash判重,结果一开始有冲突,由于本菜比较懒不想写链表,遂换了好几个Hash的方程最后终于过了

    最近刷题严重没感……

  • 0
    @ 2008-09-01 10:33:45

    编译通过...

    ├ 测试数据 01:答案错误...程序输出比正确答案长

    ├ 测试数据 02:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 03:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 04:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 05:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 06:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 07:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 08:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 09:运行时错误...| 错误号: 216 | 存取非法

    ├ 测试数据 10:运行时错误...| 错误号: 216 | 存取非法

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:0 有效耗时:0ms

    我撞棉花撞死算了

  • 0
    @ 2008-07-21 09:24:21

    古老的搜索题。。。放在现在没了空间复杂度。。当时要写很久很久+卡时的吖~~!

  • 0
    @ 2008-07-19 11:27:37

    CTSC2000 这题的第一个数据是错的

    原文讲

    冰块的起始位置与深洞的位置均不和任何冰山相邻。而官方的数据中,第一个数据的深洞与冰山相邻

  • 0
    @ 2008-07-17 10:47:54

    地下二层

  • 0
    @ 2008-07-17 07:42:47

    有没有地下室的地板啊?

  • 0
    @ 2008-07-16 21:20:23

    地下室。。

  • 1

信息

ID
1366
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
163
已通过
47
通过率
29%
上传者