题目：POJ 3126 Prime Path。

我的代码

#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 为起点，在个、十、百、千位上分别枚举替换为哪一个数字，使得替换后的数字是质数且只有一位与原数不同。

a 所有的情况被枚举完以后，继续宽搜，直到第一次搜到 b 或所有数被搜完。

如果搜到 b，直接把tot设为1，告诉程序“已经有答案了！”，就直接输出答案。如果所有数被搜完后tot还是0，则输出 Imopssible。

---

我感觉自己的做法没毛病，但调了一下午一晚上，样例都过不了。还请各位大神给我“找找茬”。谢谢！

样例	输入	标准输出	我的输出
$1$	$1033$ $8179$	$6$	$6$
$2$	$1373$ $8017$	$7$	$5$
$3$	$1033$ $1033$	$0$	$0$