自动搬运

查看原文

来自洛谷，原作者为

	EternalHeart1314 乱搞之神&常数之神&罚时之神

搬运于2025-08-24 21:51:56，当前版本为作者最后更新于2023-10-12 12:05:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

$\text{Upd on 2025.8.20}$：修改了一些神秘东西（原已过审）。

题意

要把一个冰块从 $(sx, sy)$ 推到 $(tx, ty)$。

中途有 $n$ 个冰川，推冰块时，冰块会一直朝一个方向漂移，直到推到 $(ts, ty)$ 或碰到冰川。

思路

由于冰块会一直漂移，如果我们模拟冰块漂移的话，时间复杂度肯定爆炸，因为这题它根本没给 $x$ 和 $y$ 的范围，天知道它会不会是 $10^9$，所以我们只能每次枚举所有冰川，看看冰块往四个方向分别会漂移到哪个位置。

知道了冰块会碰到那个冰川，就可以跑 BFS 了。

注意要判断冰块能直接漂移到 $(tx, ty)$ 的情况。

时间复杂度 $O(n^2)$。

目前是你谷最优解第一页。

Code

#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;
}

珍惜生命，远离抄袭