棋盘问题

GitHub跳转原题关系图返回列表

无限棋盘上按 n 个向量走最短步数,BFS 只保留贴着起终点连线走廊(宽度为单步最大长度)的点,状态数降为 O((|dx|+|dy|)·√D)。

OJ: roj

题目 ID: 1690

难度:普及+/提高-

标签:搜索BFS剪枝哈希python

创建: 2026-10-07 17:33

更新: 2026-10-07 17:33

形式化题目

棋盘可以看成整点集合 Z2\mathbb{Z}^2。给定起点 S=(fx,fy)S=(f_x,f_y)、终点 T=(tx,ty)T=(t_x,t_y), 以及 nn 个非零向量 v1,…,vn∈Z2v_1,\dots,v_n \in \mathbb{Z}^2(vi=(xi,yi)v_i=(x_i,y_i))。 一次移动把当前点 pp 变成 p+vip+v_i(可以重复使用同一个向量)。 求最小的 kk,使得存在下标序列 i1,…,iki_1,\dots,i_k 满足

S+vi1+vi2+⋯+vik=T, S + v_{i_1} + v_{i_2} + \cdots + v_{i_k} = T ,

即目标位移 Δ=T−S\Delta = T - S 能写成若干个(可重复)viv_i 之和,且使用的向量个数最少。 无解输出 IMPOSSIBLE。

输入规模:T<20T < 20 组数据,坐标满足 −5000≤fx,fy,tx,ty≤5000-5000 \le f_x,f_y,t_x,t_y \le 5000, 1≤n≤101 \le n \le 10,向量分量 1≤x,y≤101 \le x,y \le 10。

一个小判据。 因为题面保证向量分量都非负,若目标落在起点左下方 (tx<fxt_x < f_x 或 ty<fyt_y < f_y),无论怎么走都只能让坐标不减,直接不可达。 另外一个不写进代码、只用于理解的做法:若所有向量的分量都是偶数、而某个坐标差是奇数, 则由奇偶性不变可知无解——但 BFS 本身就会得出 IMPOSSIBLE,所以代码里只保留了 上面那条非负性判据。

正解

思路

朴素做法:BFS。 每个状态是一个整点,边是「加一个向量」。这是一张无权图, 从起点 BFS 第一次走到终点时的层数就是答案。

瓶颈在哪? 棋盘无限大,从 (−5000,−5000)(-5000,-5000) 走到 (5000,5000)(5000,5000) 时, BFS 会向外扩散到半径 10410^4 的区域,即约 4×1084\times 10^8 个状态;即使每步只走 (10,10), 走 1000 步的过程中如果按「所有点」展开,队列规模也是 O(步数×n)O(\text{步数} \times n) 的 多层爆炸。真正的浪费是:绝大多数被搜到的点根本不在「起点到终点」的方向上。

关键观察:最优路径可以贴着连线走。 设 L=∣T−S∣L = |T-S| 是起终点距离,vmax⁡v_{\max} 是所有向量中模长最大者, D=max⁡i∣vi∣2D = \max_i |v_i|^2。把最优解中的向量按顺序重排(向量加法可交换!), 可以证明存在一条同样长度的最优路径,其中每一时刻当前点到线段 STST 的距离不超过 vmax⁡v_{\max}。直觉:如果某一步之后点离连线太远,那么后面必然有一步要把它拉回来; 而「拉回来」这一步和「拉出去」那一步的合成位移仍然是一个合法位移,把这两步的 位置对调不会增加总步数,但会让路径更贴线。因此存在一条最优路径全程落在 走廊 {p:dist⁡(p,ST)≤D}\{p : \operatorname{dist}(p, ST) \le \sqrt{D}\} 内。

走廊的面积:长度 O(∣dx∣+∣dy∣)O(|dx| + |dy|)、宽度 O(D)O(\sqrt D),于是状态数上界约为 (∣dx∣+∣dy∣)⋅22D(|dx|+|dy|) \cdot 2\sqrt{2D}。本题 ∣dx∣+∣dy∣≤2×104|dx|+|dy| \le 2\times 10^4、D≤200D \le 200, 约 4×1054\times 10^5 个状态,可以放心 BFS。

走廊怎么判? 设连线方向 n⃗=T−S=(dx,dy)\vec n = T - S = (dx, dy),法向量 m⃗=(dy,−dx)\vec m = (dy, -dx), 连线方程 dy⋅x−dx⋅y+C=0dy \cdot x - dx \cdot y + C = 0,其中 C=fytx−fxtyC = f_y t_x - f_x t_y(代入 SS、TT 都成立)。 点 pp 到连线的距离平方为 (m⃗⋅p+C)2∣m⃗∣2\dfrac{(\vec m \cdot p + C)^2}{|\vec m|^2}, ∣m⃗∣2=dx2+dy2|\vec m|^2 = dx^2 + dy^2,与 DD 比较时把分母乘过去即可,全程整数运算不需要开方:

(m⃗⋅p+C)2≤D⋅(dx2+dy2). (\vec m \cdot p + C)^2 \le D \cdot (dx^2 + dy^2).

另外必须要求投影落在段内(而不是整条直线上):用两端点各做一次点积判方向, (T−S)⋅(p−S)≥0(T-S)\cdot(p-S) \ge 0 且 (S−T)⋅(p−T)≥0(S-T)\cdot(p-T) \ge 0 表示 pp 的投影在线段 STST 之中。 否则点会顺着连线的延长线跑到无穷远,走廊变成半无限长条。

退化情形保留。 当起终点非常近(∣T−S∣≤D|T-S| \le \sqrt D,比如起点等于终点、 或目标就在一步之内)时,走廊本身很窄甚至无宽度,而最优路径可能是先「绕远再回来」。 所以额外无条件保留起点和终点各自半径 D\sqrt D 的球内的所有点: (px−fx)2+(py−fy)2≤D(p_x-f_x)^2+(p_y-f_y)^2 \le D 或 (px−tx)2+(py−ty)2≤D(p_x-t_x)^2+(p_y-t_y)^2 \le D。 这两个球总共才 O(D)O(D) 个点,不会破坏复杂度,但覆盖了所有「短距离」情形。

去重。 走廊内的点数量级是 105∼10610^5 \sim 10^6,坐标范围 [−5000,5000][-5000,5000] 只用 104×10410^4 \times 10^4 就够放布尔表,但每次查询都要清空整张表代价太大。 可以直接用 int 坐标哈希成一个 Θ(1)\Theta(1) 的集合:C++ 手写开散列(质数 999983999983 取模 + 邻接链表),Python 直接用 set。用「是否见过」代替「记 dist」: BFS 每层推进一格,第一次弹出的终点所在层号就是答案。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:设 NN 为走廊内的状态数,N=O((∣dx∣+∣dy∣)D)N = O\big((|dx|+|dy|)\sqrt D\big), 每个状态扩展 nn 条边,故 O(Nn)O(N n)。本题 ∣dx∣+∣dy∣≤2×104|dx|+|dy| \le 2\times10^4、 D≤200D \le 200、n≤10n \le 10,NN 约 4×1054\times 10^5,单组数据为千万级常数次运算, 加上 T<20T<20 与 3000 ms 限时余量充足。
  • 空间:状态哈希表与 BFS 队列各 O(N)O(N)。C++ 用 Entry{x, y, nxt} 结构数组(10610^6 个) 加 999983999983 个桶头,共约 4×1064\times10^6 个 int ≈ 16 MB,符合 64 MB 限制; 实测峰值 10.7 MB(预分配但未全部触页)。
  • 实测(真实数据 10 点,main.cpp):最大状态数出现在点 9(答案 1000、 向量含 (10,10)),为 408 163 个状态,与上界估算吻合并正好顶到题目上限; 单点耗时 ≤ 0.025 s,峰值内存 ≤ 10.7 MB。
  • 为什么不用「数学解法」:向量的 xx、yy 分量互相耦合(不能把两个坐标拆开独立 做完全背包),且 nn 小时最优解的步数可以很大(例如单向量 (10,10) 要走 1000 步), 整数规划式的做法无法通用,BFS + 走廊剪枝是本题的标准做法。
  • Python 侧的 TLE 风险:main.py 与 C++ 同阶(都是走廊内 NN 个状态的 BFS), 但常数大很多。实测 10 组真实数据单点 ≤ 0.55 s;把真实数据里最重的点 9 (N=408 163N=408\,163)重复 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」。