一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P3716 【冰原探险】

posted on 2018-11-05 14:33:28 | under 未分类 |

这倒题目的思路真的不是很难想,要说代码实现起来也不是很困难,可能小细节比较多,而且数据范围是个大坑点......

小蒟蒻考场上就栽在负数上面了......100->30 而且看了好半天才发现可以有负数...... 小蒟蒻想着自己的坑点都顺利跳过去了,没想到出了个出了个这么大的锅,maxx的初始全设成的0......各位dalao就权当是看个笑话吧,当然如果能帮到dalao们的话那就是小蒟蒻的荣幸了qwqwq

下面讲一下具体的做法:

就是一个简单的广搜,不过如果一步一步去走的话一定会TLE,那么来考虑一下其他的方法,其实也不难像,冰块的数量不算多,可以在广搜的时候枚举所有冰块,求出距离当前点上下左右最近的冰块(没有冰块的话就返回极大或极小值),判断一下能否直接跳到终点,这里稍微讲一下,从一个点能直接跳到终点当且仅当这个点和终点在同一条线上,且中间没有任何冰块。(可以根据之前找出的当前点4个方向最近的冰块来判断当前点与终点之间是否有冰块)

至于最短时间的问题,用map保存一下状态对应的时间就行了

然后似乎也就没什么了呀qwqwq

那么代码如下:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <map>
#define maxn 100010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, z, xq, yq, xz, yz, d1, d2, d3, d4;
struct hz {
    int h;
    int l;
    inline bool operator <(const hz &o) const { //使用结构体作为map的key需要重载小于号 
        if(h == o.h)
          return l < o.l;
        return h < o.h;
    }
};

struct bs {
    int a1;
    int b1;
    int a2;
    int b2;
}ss[5000];

queue<hz> q;
map<hz, int> mmp;

inline void bfs() {
    while(!q.empty()) {
        hz hh = q.front();
        re int xx = hh.h, yy = hh.l;
        re int rt[5];  
        rt[1] = -999999999;// 一定要赋为极小值,考试就是死在这里了... 
        rt[2] = 0x7fffffff; rt[3] = -999999999; rt[4] = 0x7fffffff;
        FOR(i, 1, m) { //处理四个边界距离距离当前节点最近的冰块(是否有冰块) 
            if(ss[i].a1 <= xx && ss[i].a2 >= xx && yy > ss[i].b2)
              rt[1] = max(rt[1], ss[i].b2);
            if(ss[i].a1 <= xx && ss[i].a2 >= xx && yy < ss[i].b1)
              rt[2] = min(rt[2], ss[i].b1);
            if(ss[i].b1 <= yy && ss[i].b2 >= yy && xx < ss[i].a1)
              rt[4] = min(rt[4], ss[i].a1);
            if(ss[i].b1 <= yy && ss[i].b2 >= yy && xx > ss[i].a2)
              rt[3] = max(rt[3], ss[i].a2);
        }
        FOR(i, 1, 4) { //走这4个边界,如果可以走则加入队列 1234分别代表上下左右 
            if(i == 1) { 
                if(xx == xz && yy > yz && rt[1] < yz){ //如果能直接到达终点 
                    printf("%d", mmp[hh]);return;
                }
                if(rt[1] == -999999999) //如果没有冰块 
                  continue;
                hz hhh; hhh.h = xx; hhh.l = rt[1]+1;
                if(!mmp[hhh]) {
                    mmp[hhh] = mmp[hh] + 1;
                    q.push(hhh);
                }
            }
            if(i == 2) {
                if(xx == xz && yy < yz && rt[2] > yz) { // 同上 
                    printf("%d", mmp[hh]); return;
                }
                if(rt[2] == 0x7fffffff)
                  continue;
                hz hhh; hhh.h = xx; hhh.l = rt[2]-1;
                if(!mmp[hhh]) { //不重复走 & 记录时间 
                    mmp[hhh] = mmp[hh] + 1;
                    q.push(hhh);
                }
            }
            if(i == 3) {
                if(yy == yz && xx > xz && rt[3] < xz) { 
                    printf("%d", mmp[hh]); return;
                }
                if(rt[3] == -999999999)
                  continue;
                hz hhh; hhh.h = rt[3]+1; hhh.l = yy;
                if(!mmp[hhh]) {
                    mmp[hhh] = mmp[hh] + 1;
                    q.push(hhh);
                }
            }
            if(i == 4) {
                if(yy == yz && xx < xz && rt[4] > xz) {
                    printf("%d", mmp[hh]); return;
                }
                if(rt[4] == 0x7fffffff)
                  continue;
                hz hhh; hhh.h = rt[4]-1; hhh.l = yy;
                if(!mmp[hhh]) {  
                    mmp[hhh] = mmp[hh] + 1;
                    q.push(hhh);
                }
            }
        }
        q.pop();
    }
    printf("0");
    return;
}

int main() {
    scanf("%d", &m);
    scanf("%d%d", &xq, &yq); 
    scanf("%d%d", &xz, &yz);
    FOR(i, 1, m) {
        scanf("%d%d%d%d", &ss[i].a1, &ss[i].b1, &ss[i].a2, &ss[i].b2);
    }
    hz hh;
    hh.h = xq;
    hh.l = yq;
    q.push(hh);
    mmp[hh] = 1;
    bfs();
}