题解 P3716 【冰原探险】
Juan_feng
2018-11-05 14:33:28
这倒题目的思路真的不是很难想,要说代码实现起来也不是很困难,可能小细节比较多,**而且数据范围是个大坑点**......
**小蒟蒻考场上就栽在负数上面了......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();
}
```