题解：（蓝）P3716 [CTSC2000] 冰原探险
EternalHeart1314
·
·
题解
题目传送门
# 题意
要把一个冰块从 $(sx, sy)$ 推到 $(tx, ty)$。
中途有 $n$ 个冰川，推冰块时，冰块会一直朝**一个方向**~~漂移~~，直到推到 $(ts, ty)$ 或碰到冰川。
# 思路
由于冰块会一直漂移，如果我们模拟冰块漂移的话，时间复杂度肯定爆炸，因为这题它根本没给 $x$ 和 $y$ 的范围，天知道它会不会是 $10^9$，所以我们只能每次枚举所有冰川，看看冰块往四个方向分别会漂移到哪个位置。
知道了冰块会碰到那个冰川，就可以跑 BFS 了。
注意要判断冰块能直接漂移到 $(tx, ty)$ 的情况。
时间复杂度 $O(n^2)$。
目前是你谷最优解第一页。
# Code
```cpp
#include<iostream>
#include<queue>
#include<map>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N(4096), INF(1e9);
int n, sx, sy, tx, ty, x, y, d[4], x1[N], y1[N], x2[N], y2[N];
map <int, map<int, int> > dis;
void bfs() {
queue <pair<int, int> > q;
q.push(mp(sx, sy));
bool flag = false;
while(q.size()) {
x = q.front().fi, y = q.front().se;
q.pop();
d[0] = d[2] = -INF, d[1] = d[3] = INF;
for(int i = 1; i <= n; ++ i) {
if(x1[i] <= x && x <= x2[i]) {
if(y2[i] < y) {
d[0] = max(d[0], y2[i] + 1);
}
if(y1[i] > y) {
d[1] = min(d[1], y1[i] - 1);
}
}
if(y1[i] <= y && y <= y2[i]) {
if(x2[i] < x) {
d[2] = max(d[2], x2[i] + 1);
}
if(x1[i] > x) {
d[3] = min(d[3], x1[i] - 1);
}
}
}
if(x == tx && (ty < y && d[0] < ty || ty > y && d[1] > ty) || y == ty && (tx < x && d[2] < tx || tx > x && d[3] > tx)) {
dis[tx][ty] = dis[x][y] + 1;
return ;
}
for(int i = 0; i < 4; ++ i) {
if(d[i] != (-(i & 1) ^ -INF) + (i & 1) && !(i < 2 ? dis[x][d[i]] : dis[d[i]][y])) {
dis[i < 2 ? x : d[i]][i < 2 ? d[i] : y] = dis[x][y] + 1;
q.push(i < 2 ? mp(x, d[i]) : mp(d[i], y));
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> sx >> sy >> tx >> ty;
for(int i = 1; i <= n; ++ i) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
}
bfs();
cout << dis[tx][ty];
return 0;
}
```
### 珍惜生命，远离抄袭