Question

poj题目 问题求大神解决

poj3126 http://poj.org/problem?id=3126
我的代码是
#include<iostream>
#include<cstdlib>
#include <queue>
#include <stdlib.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int is_prime(int k)
{
for(int i=2;i*i<=k;i++)
if(k%i==0)
return 0;
return 1;
}
int vis[10005];
int a,b;
int mark;
struct node
{
int value;
int step;
}nod[10005];
void bfs()
{
queue<node>q;
node p;
p.step=0;
p.value=a;
q.push(p);

Answer 1

因为你发的代码不完整，帮你打了一遍，提交过的，Accepted

#include <queue>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
#define MAX 10000
bool prime[MAX];
bool visited[MAX];
int max_prime = 1;
struct node
{
    int value;
    int step;
};
int is_prime(int x){
    int value = (int)sqrt((double)x);
    if(x%2==0) return 0;
    int i;
    for(i=3;i<=value;i+=2)
        if(prime[i]==1 && x%i==0) return 0;
    return 1;
}
int main()
{
    prime[2]=1;prime[3]=1;
    int i;
    for(i=3;i<MAX;i+=2) if(is_prime(i)){
        prime[i] = 1;
       // printf("%d ",i);
    }
    int t;
    scanf("%d",&t);
    while(t--){
        memset(visited,0,sizeof(visited));
        queue<node> q;
        int a,b;
        scanf("%d%d",&a,&b);
        node x;
        x.step = 0;
        x.value = a;
        q.push(x);
        while(!q.empty()){
            node t = q.front();q.pop();
            if(visited[t.value]) continue;
            visited[t.value]=true;
            if(t.value==b){
                printf("%d\n",t.step);
                break;
            }
            //printf("%d,",t.value);
            int base = 1000;
            while(base>0){
                int x = t.value%base + t.value/(10*base)*(10*base);
                int i=0;
                if(base==1000) i=1000;
                for(;i<10*base;i+=base){
                    int v = x + i;
                    if(prime[v] && !visited[v]){
                        node temp;
                        temp.value = v;
                        temp.step = t.step +1;
                        q.push(temp);
                    }
                }
                base = base/10;
            }
        }
    }
    return 0;
}