题解 P3716 【冰原探险】

这倒题目的思路真的不是很难想，要说代码实现起来也不是很困难，可能小细节比较多，**而且数据范围是个大坑点**...... **小蒟蒻考场上就栽在负数上面了......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(); } ```