HDU 4255 A Famous Grid：螺旋網格 BFS 最短路徑避開質數

題目大意

無限螺旋網格：從中心 1 開始，向右、上、左、下、右... 螺旋擴展填入自然數。
只能走合數或 1 的格子，質數格子不可通行。上下左右移動。求兩非質數間最短路徑長度，或輸出 impossible。

查詢點值 ≤ 10000，多測試用例。

核心步驟

1. 預計算質數表：埃氏篩至 10000² (足夠覆蓋查詢範圍)
2. 構建網格座標映射：將數值 → (x,y) 座標。螺旋規律：層數 k 邊長 2k+1，角點值可推導
3. BFS 求最短路：在合數格子圖上 BFS

螺旋座標生成算法

從中心 (0,0) = 1 開始。第 k 層 (k≥1) 為邊長 2k+1 的正方形環。
環起始值：(2k-1)² + 1，終止值：(2k+1)²。
按右、上、左、下四邊各 2k 步填充。

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 10000;
const int MAXG = 210; // 足夠覆蓋 10000 的螺旋範圍
const int OFFSET = 105; // 坐標偏移，避免負數

bool isPrime[MAXV * MAXV + 1];
int grid[MAXG][MAXG]; // 座標 → 數值
int dist[MAXG][MAXG];
pair pos[MAXV + 1]; // 數值 → 座標

void sieve() {
    fill(isPrime, isPrime + MAXV*MAXV + 1, false);
    isPrime[0] = isPrime[1] = true;
    for (int i = 2; i*i <= MAXV*MAXV; ++i)
        if (!isPrime[i])
            for (int j = i*i; j <= MAXV*MAXV; j += i)
                isPrime[j] = true;
    isPrime[1] = false; // 1 視為合數/可通行
}

void buildSpiral() {
    int x = OFFSET, y = OFFSET;
    int val = 1;
    grid[x][y] = val;
    pos[val] = {x, y};

    for (int layer = 1; val <= MAXV; ++layer) {
        int step = 2*layer;
        // 右
        for (int i = 0; i < step && val < MAXV; ++i) {
            ++y; grid[x][y] = ++val; pos[val] = {x, y};
        }
        // 上
        for (int i = 0; i < step && val < MAXV; ++i) {
            --x; grid[x][y] = ++val; pos[val] = {x, y};
        }
        // 左
        for (int i = 0; i < step && val < MAXV; ++i) {
            --y; grid[x][y] = ++val; pos[val] = {x, y};
        }
        // 下
        for (int i = 0; i < step && val < MAXV; ++i) {
            ++x; grid[x][y] = ++val; pos[val] = {x, y};
        }
    }
}

int bfs(int sx, int sy, int tx, int ty) {
    if (sx == tx && sy == ty) return 0;
    memset(dist, -1, sizeof(dist));
    queue> q;
    q.emplace(sx, sy);
    dist[sx][sy] = 0;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= MAXG || ny < 0 || ny >= MAXG) continue;
            int val = grid[nx][ny];
            if (val == 0 || isPrime[val]) continue; // 未填充或質數
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            if (nx == tx && ny == ty) return dist[nx][ny];
            q.emplace(nx, ny);
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    buildSpiral();

    int x, y, tc = 0;
    while (cin >> x >> y) {
        if (!grid[pos[x].first][pos[x].second] || !grid[pos[y].first][pos[y].second]) {
            cout << "Case " << ++tc << ": impossible\n";
            continue;
        }
        if (isPrime[x] || isPrime[y]) {
            cout << "Case " << ++tc << ": impossible\n";
            continue;
        }
        auto [sx, sy] = pos[x];
        auto [tx, ty] = pos[y];
        int d = bfs(sx, sy, tx, ty);
        cout << "Case " << ++tc << ": " << (d == -1 ? "impossible" : to_string(d)) << '\n';
    }
    return 0;
}

關鍵優化點

複雜度分析

• 預計算：篩 O(V log log V) ≈ 10⁸ 略大，實際只需篩到網格最大值 (≈ 210²/2 ≈ 22000)；螺旋構建 O(V)
• 單次 BFS：O(網格面積) ≈ 4×10⁴，極快
• 總時間：預計算主導，單次查詢極快

總結

HDU 4255 綜合考察數論 (質數篩)、幾何映射 (螺旋座標)、圖論 (BFS 最短路)。關鍵在於正確生成螺旋座標映射，並將「質數不可通行」轉化為圖中節點刪除。預計算 + BFS 模式適用於所有「靜態圖多查詢最短路」問題。