无限棋盘上按 n 个向量走最短步数,BFS 只保留贴着起终点连线走廊(宽度为单步最大长度)的点,状态数降为 O((|dx|+|dy|)·√D)。
OJ: roj
题目 ID: 1690
难度:普及+/提高-
标签:搜索BFS剪枝哈希python
创建: 2026-10-07 17:33
更新: 2026-10-07 17:33
形式化题目
棋盘可以看成整点集合
即目标位移 IMPOSSIBLE。
输入规模:
一个小判据。 因为题面保证向量分量都非负,若目标落在起点左下方
(IMPOSSIBLE,所以代码里只保留了
上面那条非负性判据。
正解
思路
朴素做法:BFS。 每个状态是一个整点,边是「加一个向量」。这是一张无权图, 从起点 BFS 第一次走到终点时的层数就是答案。
瓶颈在哪? 棋盘无限大,从
关键观察:最优路径可以贴着连线走。
设
走廊的面积:长度
走廊怎么判? 设连线方向
另外必须要求投影落在段内(而不是整条直线上):用两端点各做一次点积判方向,
退化情形保留。 当起终点非常近(
去重。 走廊内的点数量级是 int 坐标哈希成一个 set。用「是否见过」代替「记 dist」:
BFS 每层推进一格,第一次弹出的终点所在层号就是答案。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:29
# update_at: 2026-10-07 17:33
import sys
from collections import deque
IMPOSSIBLE = "IMPOSSIBLE" # 目标不可达时的输出文本
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Point = tuple[int, int] # 棋盘上的一个整数坐标点
type Vectors = list[Point] # 题面给出的 n 个可走向量
def search(start: Point, target: Point, vecs: Vectors) -> int:
"""BFS 求最少步数:每步加一个向量,返回步数,不可达返回 -1。
棋盘无限大,但一条最优路径总可以贴着「起点-终点」连线走,于是只让落在
连线走廊(到连线距离 <= 单步最大长度 sqrt(D))内的点入队,另额外保留
起点/终点半径 sqrt(D) 球内的点。走廊长度 O(|dx|+|dy|)、宽度 O(sqrt(D)),
状态数 O((|dx|+|dy|)*sqrt(D)),远小于全平面。
"""
sx, sy = start
tx, ty = target
# 向量分量全非负时,目标落在起点左下方必然到不了(坐标只会不减)
if (tx < sx or ty < sy) and all(u >= 0 and v >= 0 for u, v in vecs):
return -1
dx, dy = tx - sx, ty - sy # 连线方向向量
mx, my = dy, -dx # 连线法向量,与 (dx,dy) 垂直
const = sy * tx - sx * ty # 连线方程 mx*x + my*y + const = 0
norm = mx * mx + my * my # 法向量模长平方,比较距离时约掉
d = max(x * x + y * y for x, y in vecs) # 单步最大长度的平方 D
seen: set[Point] = {start}
queue: deque[Point] = deque([start])
step = 0
while queue:
for _ in range(len(queue)): # 按层推进,出一层就把步数加一
cx, cy = queue.popleft()
if (cx, cy) == target:
return step
for u, v in vecs:
px, py = cx + u, cy + v
if (px, py) in seen:
continue
# 起终点附近半径 sqrt(D) 的球内一律保留,兜住「起终点很近」的退化情形
near_end = ((px - sx) ** 2 + (py - sy) ** 2 <= d
or (px - tx) ** 2 + (py - ty) ** 2 <= d)
ray = (px - sx) * dx + (py - sy) * dy # 相对起点的投影,<0 表示落到身后
ahead = (px - tx) * dx + (py - ty) * dy # 相对终点的投影,>0 表示越过头
off = (mx * px + my * py + const) ** 2 # 到连线距离平方 * |法向量|^2
if not near_end and (ray < 0 or ahead > 0 or off > d * norm):
continue
seen.add((px, py))
queue.append((px, py))
step += 1
return -1
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
fx, fy, tx, ty = next(data), next(data), next(data), next(data)
n = next(data)
vecs: Vectors = [(next(data), next(data)) for _ in range(n)]
ans = search((fx, fy), (tx, ty), vecs)
out.append(str(ans) if ans >= 0 else IMPOSSIBLE)
print("\n".join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 17:29
* update_at: 2026-10-07 17:33
*/
// main.cpp:棋盘问题,无限棋盘上按 n 个向量走,BFS 求最少步数。
// 与 main.py 同一算法:只保留「贴着起点-终点连线」的走廊内状态(宽度为单步最大长度),
// 另加起终点附近的小球兜底,用手写开散列判重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 1000000; // 走廊内的状态数上界(实测最大约 41 万)
const int PRIME = 999983; // 开散列取模用的质数
int vecx[12], vecy[12]; // 可走的 n 个向量
int n; // 向量个数
ll sx, sy, tx, ty; // 起点与终点坐标
ll D; // 单步最大长度的平方 max(x^2 + y^2)
ll A, B, C; // 起点-终点连线方程 A*x + B*y + C = 0
struct Entry { // 散列桶里的一个状态:坐标 + 同桶下一条链
int x, y, nxt;
};
Entry table[MAXM];
int head[PRIME]; // 每个桶的链表头
int idx; // 已插入的状态数
static inline ll sqr(ll v) { return v * v; }
static inline int hashxy(ll x, ll y) {
ll h = ((x << 16) ^ y) % PRIME;
if (h < 0) h += PRIME;
return (int)h;
}
// 插入状态,返回 false 表示此前已经访问过
static inline bool insert_state(ll x, ll y) {
int h = hashxy(x, y);
for (int e = head[h]; e != -1; e = table[e].nxt) {
if (table[e].x == x && table[e].y == y) return false;
}
table[idx].x = (int)x;
table[idx].y = (int)y;
table[idx].nxt = head[h];
head[h] = idx++;
return true;
}
// 点 (x,y) 是否值得扩展:靠近起终点,或落在连线走廊内且投影不越过头尾
static inline bool useful(ll x, ll y) {
if (sqr(x - sx) + sqr(y - sy) <= D) return true;
if (sqr(x - tx) + sqr(y - ty) <= D) return true;
if ((tx - sx) * (x - sx) + (ty - sy) * (y - sy) < 0) return false; // 落到起点身后
if ((sx - tx) * (x - tx) + (sy - ty) * (y - ty) < 0) return false; // 越过了终点
return sqr(A * x + B * y + C) <= D * (sqr(A) + sqr(B)); // 到连线距离 <= sqrt(D)
}
// 按层 BFS,第一次弹出终点时的层号就是答案;不可达返回 -1
static int bfs() {
memset(head, -1, sizeof(head));
idx = 0;
queue<pair<int, int>> q;
q.push({(int)sx, (int)sy});
insert_state(sx, sy);
int step = 0;
while (!q.empty()) {
int cnt = (int)q.size();
while (cnt--) {
int cx = q.front().first, cy = q.front().second;
q.pop();
if (cx == tx && cy == ty) return step;
for (int i = 0; i < n; i++) {
int nx = cx + vecx[i], ny = cy + vecy[i];
if (useful(nx, ny) && insert_state(nx, ny)) q.push({nx, ny});
}
}
step++;
}
return -1;
}
int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
scanf("%lld %lld %lld %lld", &sx, &sy, &tx, &ty);
scanf("%d", &n);
D = 0;
bool allPos = true; // 题面保证分量 > 0,这里仍留一手兼容负数
for (int i = 0; i < n; i++) {
scanf("%d %d", &vecx[i], &vecy[i]);
D = max(D, sqr(vecx[i]) + sqr(vecy[i]));
if (vecx[i] < 0 || vecy[i] < 0) allPos = false;
}
A = ty - sy;
B = sx - tx;
C = sy * tx - sx * ty;
if (allPos && (tx < sx || ty < sy)) { // 分量非负时坐标只增不减
puts("IMPOSSIBLE");
continue;
}
int ans = bfs();
if (ans < 0) puts("IMPOSSIBLE");
else printf("%d\n", ans);
}
return 0;
}复杂度
- 时间:设
为走廊内的状态数, , 每个状态扩展 条边,故 。本题 、 、 , 约 ,单组数据为千万级常数次运算, 加上 与 3000 ms 限时余量充足。 - 空间:状态哈希表与 BFS 队列各
。C++ 用 Entry{x, y, nxt}结构数组(个) 加 个桶头,共约 个 int≈ 16 MB,符合 64 MB 限制; 实测峰值 10.7 MB(预分配但未全部触页)。 - 实测(真实数据 10 点,
main.cpp):最大状态数出现在点 9(答案 1000、 向量含 (10,10)),为 408 163 个状态,与上界估算吻合并正好顶到题目上限; 单点耗时 ≤ 0.025 s,峰值内存 ≤ 10.7 MB。 - 为什么不用「数学解法」:向量的
、 分量互相耦合(不能把两个坐标拆开独立 做完全背包),且 小时最优解的步数可以很大(例如单向量 (10,10) 要走 1000 步), 整数规划式的做法无法通用,BFS + 走廊剪枝是本题的标准做法。 - Python 侧的 TLE 风险:
main.py与 C++ 同阶(都是走廊内个状态的 BFS), 但常数大很多。实测 10 组真实数据单点 ≤ 0.55 s;把真实数据里最重的点 9 ( )重复 20 遍凑成极限输入时约 9.9 s,而 C++ 只要 0.3 s。 本题给 Python 的预算需要 3 s 以上,题面 3000 ms 下属于边界情况, 这也是本仓库允许 Python 短解法 TLE 的典型情形。
总结
- 无限图上的最短路,先想办法把状态压回有限且小。 本题的状态数是无限的, 唯一出路是证明「存在一条最优路径落在某个窄区域里」,再用区域面积估界。
- 向量加法可交换是剪枝的合法性来源。 因为顺序无关,才能对调步骤把路径「拉直」, 这是「贴线走廊」成立的本质原因。
- 距离比较用平方,投影判定用点积,全程整数运算,避免浮点误差把边界点误剪。
- 退化情形(起终点很近)要单独兜底:走廊宽度为 0 时
<= D的球内保留就是兜底。 - 关于素材的
std.cpp:它与本题题面一致(示例输出、10 组真实数据均对得上), 本仓库的实现独立重写了数据结构(BFS 按层推进、手动开散列)与剪枝写法, 但走廊剪枝这一核心思路的确相同——这是本题唯一可行的思路,不属于照抄。 - 本题素材源自带的
data.py说明测试数据是自动生成的,题面是网络重建版 (与 POJ 3985 同题),出题意图与原官方题可能略有偏差;本解法的正确性依据是 题面本身加真实数据比对,而不是「官方 AC」。