有关素数和距离的宽搜

#include <cstdio>
#include <cstring>
using namespace std;
int T,a,b;
const int maxn=1e4;
int prime[maxn],cnt;
int vis[maxn],tot;        //0表示是素数，1表示是合数
int dis[maxn];
int q[maxn],h,t,aa,aaa,aaaa;//q是数组模拟的队列
int vv[maxn];
void get_prime(int n)//欧拉筛，在洛谷过了，没问题
{
    for(int i=2;i<n;++i)
    {        //这里直接跳过1
        if(!vis[i])
            prime[cnt++]=i;    //记录素数
        for(int j=0;j<cnt&&i<=n/prime[j];++j)
        {
            vis[i*prime[j]]=1;
            if (i%prime[j]==0)//避免重复筛选
                break;
        }
    }
}
int main()
{
    get_prime(10000);
    scanf("%d",&T);
    while(T--)
    {
        memset(vv,0,sizeof(vv));
        t=h=0;
        tot=0;//不初始化见祖宗
        scanf("%d%d",&a,&b);
        if(a==b)
        {
            printf("0\n");
            continue;//泰裤辣！
        }
        memset(dis,0,sizeof(dis));
        vv[a]=1;
        q[0]=a;
        while(t<=h)
        {
            if(tot)break;
            aa=q[t];
            ++t;
            for(int i=1;i<10000;i*=10)
            {
                if(tot)break;
                aaa=aa-aa%(i*10)/i*i;//枚举嘎掉哪一位（试过，这应该没毛病）
                for(int j=0;j<10;++j)//枚举把哪一位换成多少
                {
                    aaaa=aaa+j*i;
                    if(aaaa==aa||vis[aaaa]||vv[aaaa])continue;
                    q[h]=aaaa;
                    ++h;
                    dis[aaaa]=dis[aa]+1;
                    vv[aaaa]=1;
                    if(aaaa==b)
                    {
                        tot=1;
                        break;
                    }
                }
            }
        }
        if(tot)printf("%d\n",dis[b]);
        else printf("Impossible\n");
    }
    return 0;
}

我的主要思路（可能错）
以初始值a为起点，枚举每个位被改的情况进行宽搜。
还请各位给我“找找茬”，我调了一下午加一晚上了！

写回答
好问题 0 提建议
追加酬金
关注问题
分享
邀请回答
编辑收藏删除
收藏举报

1条回答默认最新

CSDN-Ada助手 CSDN-AI 官方账号 2023-10-18 09:21

关注

【以下回答由 GPT 生成】

这段代码可以进行以下方面的优化：

使用预处理素数表的方式来优化查找素数的过程。当前代码中使用了一个数组来存储素数，并且通过循环来判断一个数是否为素数。可以事先生成好一个素数表，并直接通过查表的方式来判断一个数是否为素数。这样可以减少循环的次数。
使用队列的方式来进行广度优先搜索（BFS）。当前代码使用两个指针t和h来模拟队列的操作。可以改为使用STL中的队列来简化代码。
使用bit数组来代替布尔数组。当前代码中使用一个布尔数组来标记某个数是否已经被访问过。可以改为使用bit数组来节省空间。
使用位运算来替代乘除法和取模运算。当前代码中有一部分涉及到乘除法和取模运算的地方。可以尝试使用位运算来提高效率。
代码可读性和可维护性的优化。当前代码的命名和代码结构不够清晰，可以对变量和函数进行合理的命名，以及优化代码的结构和注释，使代码更易读和易于维护。

以下是对上述优化的部分代码示例：

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 1e4;
const int prime_maxn = 10000;

bitset<prime_maxn> isPrime; // 使用bit数组来判断一个数是否为素数
int dis[maxn];
int vv[maxn];

void getPrime() {
    isPrime.set(); // 初始化所有数为素数
    isPrime[0] = isPrime[1] = 0; // 0和1不是素数
    for (int i = 2; i * i < prime_maxn; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j < prime_maxn; j += i) {
                isPrime[j] = 0; // 将i的倍数标记为非素数
            }
        }
    }
}

int bfs(int start, int end) {
    memset(vv, 0, sizeof(vv));
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(start);
    vv[start] = 1;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        if (cur == end) {
            return dis[cur];
        }

        for (int i = 1; i < 10000; i *= 10) {
            for (int j = 0; j < 10; ++j) {
                int next = cur - cur % (i * 10) / i * i + i * j;
                if (isPrime[next] && dis[next] == 0) {
                    dis[next] = dis[cur] + 1;
                    q.push(next);
                }
            }
        }
    }

    return -1;
}

int main() {
    getPrime();
    int T;
    scanf("%d", &T);

    while (T--) {
        int a, b;
        scanf("%d%d", &a, &b);

        if (a == b) {
            printf("0\n");
            continue;
        }

        int result = bfs(a, b);
        if (result != -1) {
            printf("%d\n", result - 1);
        } else {
            printf("-1\n");
        }
    }

    return 0;
}