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

· · 题解

观察题目的数据范围，发现 1 \le a_{i,j} \le 10000，根据我们的做题经验，如果最终时间复杂度不和 a_{i,j} 的大小相关，那出题人完全可以将数据范围设置为 1 \le a_{i,j} \le 10^9 甚至更大，但并没有。这代表这题很有可能最终时间复杂度和 a_{i,j} 的大小相关。

继续思考，我们注意到答案一定是 a_{1,1} 的因数，这是因为路径起点是 a_{1,1}，所以 a_{1,1} 一定会被经过。而我们有注意到在 1 到 10000 之前的数，因数最多的数也只有 64 个因数，这点可以用数学知识或写个代码得到，这就意味着答案最多只有 64 种可能。这启发我们可以枚举答案，然后寻找有没有一条路经，使得这个路径上的每一个数都是我们枚举的答案的倍数，这里可以用 bfs 或 dp 实现，时间复杂度均为 O(n^2)，整个题的时间复杂度为 O(d(a_{1,1})n^2)，足以通过此题。

::::info[用 dp 实现的代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
int a[N][N],b[N][N],f[N][N];
void solve(){
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int l=a[1][1];l>=1;l--){
        if(a[1][1]%l!=0)
            continue;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                b[i][j]=f[i][j]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(a[i][j]%l==0)
                    b[i][j]=1;
                else
                    b[i][j]=0;
            }
        f[1][1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(i==1&&j==1)
                    continue;
                if((f[i-1][j]==1||f[i][j-1]==1)&&b[i][j]==1)
                    f[i][j]=1;
            }
        if(f[n][n]==1){
            cout<<l;
            break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)
        solve();
}

::::

::::info[用 bfs 实现的代码，需要注意常数]

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=1005;
int a[N][N],b[N][N],vis[N][N];
void solve(){
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int l=a[1][1];l>=1;l--){
        if(a[1][1]%l!=0)
            continue;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                b[i][j]=vis[i][j]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(a[i][j]%l==0)
                    b[i][j]=1;
                else
                    b[i][j]=0;
            }
        queue<pair<int,int> > q;
        q.push({1,1});
        vis[1][1]=1;
        while(!q.empty()){
            int x=q.front().first,y=q.front().second;
            if(x==n&&y==n){
                cout<<l;
                return ;
            }
            q.pop();
            int nx,ny;
            nx=x+1,ny=y;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!vis[nx][ny]&&b[nx][ny]==1){
                vis[nx][ny]=1;
                q.push({nx,ny});
            }
            nx=x,ny=y+1;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!vis[nx][ny]&&b[nx][ny]==1){
                vis[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    while(t--)
        solve();
}

::::