筛质数的模板写错了 从1开始的变化 导致一直wa

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int prime[N], cnt;
bool st[N];
int vis[N];
void work(int n)
{
    for (int i=2;i<=n;i++) 
    {
        if (!st[i]) prime[cnt++]=i;
        for (int j=0;j<cnt&&prime[j]<=n/i;j++){
            st[i*prime[j]]=true;
            if (i%prime[j]==0) break;
        }
    }
}
int change(int t, int pos, int j)
{
    if (pos == 0) {
        if (j == 0) return 0;
        int last = t % 1000;
        return j * 1000 + last;
    }
    if (pos == 1) {
        int last = t % 100;
        int pre = t / 1000;
        return pre * 1000 + j * 100 + last;
    }
    if (pos == 2) {
        int last = t % 10;
        int pre = t / 100;
        return pre * 100 + j * 10 + last;
    }
    if (pos == 3) {
        int pre = t / 10;
        return pre * 10 + j;
    }
}
int bfs(int a, int b)
{
    // string sa=to_string(a),sb=to_string(b);
    queue<int> q;
    q.push(a);
    vis[a]=0;
    // cout << sa << sb;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        // cout << t;
        if (t == b) return vis[t];

        for (int i=0;i<4;i++) {
            for (int j=0;j<=9;j++) {
                int nt = change(t,i,j);
                if (nt == 0) continue;
                if (nt == t) continue;
                if (vis[nt]==-1&&!st[nt]&&nt!=t) {
                    // cout << nt << endl;
                    q.push(nt);
                    vis[nt]=vis[t] + 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    int T; cin >> T;
    work(10000);
    // cout << st[6033];
    while (T--) {
        memset(vis,-1,sizeof vis);
        int a,b; cin>>a>>b;
        cout<<bfs(a, b)<<endl;
    }
}

map拉满时间复杂度 可以只把change操作改一下 只有那里用string 其他地方不用

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int prime[N], cnt;
bool st[N];
unordered_map<string,int> mp;
void work(int n)
{
    for (int i=2;i<=n;i++) 
    {
        if (!st[i]) prime[cnt++]=i;
        for (int j=0;j<cnt&&prime[j]<=n/i;j++){
            st[i*prime[j]]=true;
            if (i%prime[j]==0) break;
        }
    }
}
string change(string t, int pos, int j)
{
    if (pos == 0) {
        if (j == 0) return "";
        t[0] = (j+'0');
        return t;
    }
    if (pos == 1) {
        t[1] = (j+'0');
        return t;
    }
    if (pos == 2) {
        t[2] = (j+'0');
        return t;
    }
    if (pos == 3) {
        t[3] = (j+'0');
        return t;
    }
}
int bfs(int a, int b)
{
    string sa=to_string(a),sb=to_string(b);
    queue<string> q;
    q.push(sa);
    mp[sa] = 1;
    // cout << sa << sb;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        // cout << t;
        if (t == sb) return mp[t]-1;

        for (int i=0;i<4;i++) {
            for (int j=0;j<=9;j++) {
                string nt = change(t,i,j);
                // cout << nt;
                if (nt == "") continue;
                if (nt == t) continue;
                if (mp[nt]==0&&!st[atoi(nt.c_str())]&&nt!=t) {
                    // cout << nt << endl;
                    q.push(nt);
                    mp[nt]=mp[t] + 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    int T; cin >> T;
    work(10000);
    // cout << st[6033];
    while (T--) {
        // memset(vis,-1,sizeof vis);
        mp.clear();
        int a,b; cin>>a>>b;
        cout<<bfs(a, b)<<endl;
    }
}