[题目] Luogu P3716 [CTSC2000]冰原探险-白红宇

[题目] Luogu P3716 [CTSC2000]冰原探险

阅读量：4686 次

发布时间：2019-06-09

本文共 4008 字，大约阅读时间需要 13 分钟。

题面

题目背景

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

题目描述

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

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

输入格式：

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

输出格式：

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

说明

1<=N<=4000

思路

关键: 1.map key取2个值更方便 2.各种判断条件细节推导

主要思路就是要模拟出冰块再地图中直接移动到停下的点的状态来进行bfs当前位置(x,y) 目标位置(ex,ey)上 x1<=x<=x2 && max {y2} -> (x,y2+1)下 x1<=x<=x2 && min {y1} -> (x,y1-1)左 y1<=y<=y2 && max {x2} -> (x2+1,y)右 y1<=y<=y2 && min {x1} -> (x1-1,y)+ && 冰山的位置要与去的方向一致1.冰山要在方向的那一边,与方向一致2.下个点不能在原地3.map对坐标判重4.找不到时数值为inf,不能向后走但不影响判断答案，因为inf时一定满足逻辑式5.可以画图，写出来判断式后套bfs框架即可6.每次向后走时直接枚举每一个冰山

代码

#include 
    
     #include 
     
      #include 
      #define re register#define int long longusing namespace std;const int inf = 1e9;const int maxq = 2000005;int n,bx,by,ex,ey,ans;struct f {    int x,y;    bool operator < (const f &r) const{        if(x == r.x) return y < r.y;        return x < r.x;    }};map
       
         mp;struct node {    int x,y,step;}q[maxq];int head,tail;struct point {    int x1,y1,x2,y2;}p[5005];inline void Bfs(){    head = 0, tail = 1;    q[1].x = bx, q[1].y = by, q[1].step = 0;    mp[(f){bx,by}] = 1;    while(head < tail)    {        head++; if(head >= maxq) head = 1;        int x = q[head].x, y = q[head].y, step = q[head].step;//      cout << x <<" " << y << " " << step << endl;        //上        int y2 = -inf;        for(re int i = 1; i <= n; i++)            if(p[i].x1 <= x && x <= p[i].x2 && p[i].y2 > y2 && p[i].y2 < y)                y2 = p[i].y2;        if(x == ex && ey > y2 && ey < y) {            ans = step + 1;            return;        }        if(y2 != -inf && mp[(f){x,y2+1}] == 0) {            tail++; if(tail >= maxq) tail = 1;            q[tail].x = x, q[tail].y = y2 + 1, q[tail].step = step + 1;            mp[(f){x,y2+1}] = 1;        }        //下        int y1 = inf;        for(re int i = 1; i <= n; i++)            if(p[i].x1 <= x && x <= p[i].x2 && p[i].y1 < y1 && p[i].y1 > y)                y1 = p[i].y1;        if(x == ex && ey < y1 && ey > y) {            ans = step + 1;            return;        }        if(y1 != inf && mp[(f){x,y1-1}] == 0) {            tail++; if(tail >= maxq) tail = 1;            q[tail].x = x, q[tail].y = y1 - 1, q[tail].step = step + 1;            mp[(f){x,y1-1}] = 1;        }        //左        int x2 = -inf;        for(re int i = 1; i <= n; i++)            if(p[i].y1 <= y && y <= p[i].y2 && p[i].x2 > x2 && p[i].x2 < x)                x2 = p[i].x2;        if(y == ey && ex > x2 && ex < x) {            ans = step + 1;            return;        }        if(x2 != -inf && mp[(f){x2+1,y}] == 0) {            tail++; if(tail >= maxq) tail = 1;            q[tail].x = x2 + 1, q[tail].y = y, q[tail].step = step + 1;            mp[(f){x2+1,y}] = 1;        }        //右        int x1 = inf;        for(re int i = 1; i <= n; i++)            if(p[i].y1 <= y && y <= p[i].y2 && p[i].x1 < x1 && p[i].x1 > x)                x1 = p[i].x1;        if(y == ey && ex < x1 && ex > x) {            ans = step + 1;            return;        }        if(x1 != inf && mp[(f){x1-1,y}] == 0) {            tail++; if(tail >= maxq) tail = 1;            q[tail].x = x1 - 1, q[tail].y = y, q[tail].step = step + 1;            mp[(f){x1-1,y}] = 1;        }    }}signed main(){    scanf("%lld", &n);    scanf("%lld%lld%lld%lld", &bx, &by, &ex, &ey);    for(int i = 1; i <= n; i++)        scanf("%lld%lld%lld%lld", &p[i].x1, &p[i].y1, &p[i].x2, &p[i].y2);    Bfs();    printf("%lld\n", ans);    return 0;}

转载于:https://www.cnblogs.com/colorfulmist/p/10162426.html

你可能感兴趣的文章