F题直接DP做法

考虑倒着递推，从 递推到

假设当前数字为 now 此时的状态转移方程是：dp[i][j]=std::min(dp[i][j+1],dp[i+1][j])+1

再考虑使用传送门，我们另外开一个数组 vector<int>minDis(n+1)记录使用当前质因数传送门到达终点的最短距离，此时的状态转移方程为：dp[i][j]=std::min(dp[i][j],minDis[k]+1)，其中 k 遍历 now 的所有质因数

最后由于所有 now 的质因数都可以通过 dp[i][j] 的步数到达终点，我们再将此时的 dp[i][j] 提供给 minDis，即：minDis[k]=std::min(minDis[k],dp[i][j])，其中 k 遍历所有 now 的质因数

最后输出 dp[1][1] 即可

完整代码

#include <bits/stdc++.h>
using std::cin,std::cout,std::vector,std::array;
#define endl "\n"
#define ALL(x) x.begin(),x.end()
typedef long long ll;
typedef std::pair<int,int> PII;
typedef std::tuple<int,int,int> T3I;

template <typename T>
inline void read(T &x) {
    x=0; bool f=false; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') f=true; c=getchar(); }
    while(c>='0'&&c<='9'){ x=(x*10)+(c^48); c=getchar(); }
    if(f) x=-x;
}
template <typename T, typename ...Args>
inline void read(T &tmp,Args &...tmps){ read(tmp); read(tmps...); }

std::vector<bool>vis;
std::vector<long long>prime;
auto init=[]{
    int n=1e5;
    vis.resize(n+1,true);
    vis[1]=false;
    for(int i=2;i<=n;++i){
        if(vis[i]) prime.emplace_back(i);
        for(auto &j:prime){
            if(i*j>n) break;
            vis[i*j]=false;
            if(i%j==0) break;
        }
    }
    return 0;
}();

void solve()
{
    int n,m; read(n,m);
    vector<vector<int>>adj(n+1,vector<int>(m+1));
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) read(adj[i][j]);
    vector<vector<int>>dp(n+1,vector<int>(m+1,1e9));
    dp[n][m]=0;
    vector<int>minDis(int(1e5)+1,100000);
    for(int i=n;i;--i) for(int j=m;j;--j){
        if(i<n) dp[i][j]=std::min(dp[i][j],dp[i+1][j]+1);
        if(j<m) dp[i][j]=std::min(dp[i][j],dp[i][j+1]+1);
        int now=adj[i][j];
        vector<int>dis;
        if(vis[now]) dis.emplace_back(now);
        else{
            for(int k=2;k*k<=now;++k){
                if(now%k) continue;
                dis.emplace_back(k);
                while(now%k==0) now/=k;
            }
            if(now>1) dis.emplace_back(now);
        }
        for(auto &k:dis) dp[i][j]=std::min(dp[i][j],minDis[k]+1);
        for(auto &k:dis) minDis[k]=std::min(minDis[k],dp[i][j]);
    }
    cout<<dp[1][1]<<endl;
}

int main()
{
    int T=1; // read(T);
    while(T--) solve();
    return 0;
}