题解：P16343 [科大国创杯初中组 2026] 行走

wang2025 · 2026-04-25 10:21:22 · 题解

::::info[算法提示] 算法独特，请谨慎食用！

目测 BFS，标签 DP，我 Dijkstra。 ::::

解法思路：

我们可以把问题转化为图论中的最大瓶颈路问题：

• 每个格子是一个节点
• 从 (i,j) 到 (i+1,j) 和 (i,j+1) 有边
• 边的“权重”不是固定值，而是最大公约数

使用优先队列（最大堆）来扩展状态，使用最大堆，总是优先扩展当前 g 值最大的状态，记录每个格子已经达到的所有 g 值，避免重复扩展。

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

int a, b;
int c[1005][1005];
unordered_set<int> d[1005][1005];

struct e {
    int f, g;
    int h;

    bool operator<(const e& i) const {
        return h < i.h;
    }
};

int j() {
    priority_queue<e> k;

    int l = c[1][1];
    d[1][1].insert(l);
    k.push({1, 1, l});

    int m = 0;

    while (!k.empty()) {
        e n = k.top();
        k.pop();

        int o = n.f;
        int p = n.g;
        int q = n.h;

        if (o == a && p == a) {
            m = max(m, q);
            continue;
        }

        if (o < a) {
            int r = __gcd(q, c[o + 1][p]);
            if (d[o + 1][p].find(r) == d[o + 1][p].end()) {
                d[o + 1][p].insert(r);
                k.push({o + 1, p, r});
            }
        }

        if (p < a) {
            int s = __gcd(q, c[o][p + 1]);
            if (d[o][p + 1].find(s) == d[o][p + 1].end()) {
                d[o][p + 1].insert(s);
                k.push({o, p + 1, s});
            }
        }
    }

    return m;
}

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

    cin >> a >> b;
    for (int t = 1; t <= a; t++) {
        for (int u = 1; u <= a; u++) {
            cin >> c[t][u];
        }
    }

    int v = j();
    cout << v << "\n";

    return 0;
}