（复习次数：1）Prime Path POJ3126

http://poj.org/problem?id=3126
注意：在用的同时标记走过
注意：循环的次数
注意：不能破坏数组

#include <cstdio>
#include <cstring>
#include<queue>
#define N 10005
using namespace std;
int p[N],vis[N];
struct node{
    int value,step;
}now;
int first,last;
void pre(void){
    memset(p,0,sizeof(p));for(int i=2;i<N;i++)if(!p[i])for(int k=2*i;k<N;k+=i)p[k]=1;	
}
#define go();\ if(!vis[next.value]){\next.step=now.step+1;\que.push(next);\vis[next.value]=1;}
void bfs(){
    node next;queue<node>que;que.push({
    first,0});vis[first]=1;while(!que.empty()){
    now=que.front();que.pop();if(now.value==last){
    printf("%d\n",now.step);return;}for(int i=0;i<=9;i++){
    next.value=now.value/10*10+i;go();}for(int i=0;i<=9;i++){
    next.value= now.value / 100 * 100 + i * 10 + now.value % 10;go();}for(int i=0;i<=9;i++){
    next.value=now.value/1000*1000+i*100+now.value%100;go();}for(int i=1;i<=9;i++){
    next.value=now.value%1000+i*1000;go();}}
}
int main()
{
     pre();int t;scanf("%d",&t);while(t--){
    memcpy(vis,p,sizeof(p));//1不可 scanf("%d%d",&first,&last);bfs(); }return 0;
}

复习：
5/19
还是要想清楚，磨刀不误砍柴工
用了线性筛

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
#ifdef LOCAL
FILE*fp=freopen("text.in","r",stdin);
#endif
#define N 10005
int vis[N],prime[N],book[N],cnt=0;
void pre(){
    for(int i=2;i<N;i++){
    if(vis[i]==0)prime[++cnt]=i;for(int j=1;j<=cnt;j++){
    if(i*prime[j]>=N)break;vis[i*prime[j]]=1;if(!(i%prime[j]))break;}}
}
int main(){
    pre();//for(int i=1;i<=cnt;i++)printf("%d\n",prime[i]);int t;scanf("%d",&t);while(t--){
    memset(book,-1,sizeof(book));int a,b;scanf("%d%d",&a,&b);int flag=-1;if(a==b){
    printf("0\n");continue;}queue<int>q;book[a]=0;q.push(a);while(!q.empty()){
    int now=q.front();q.pop();for(int j=0;j<4;j++){
    int t=pow(10,j);int start=now-now/t%(10)*t;for(int i=0;i<=9;i++){
    if(j==3&&i==0)continue;int temp=start+i*t;if(vis[temp]==1||book[temp]!=-1)continue;//printf("%d\n",temp);book[temp]=book[now]+1;if(temp==b){
    flag=book[temp];break;}q.push(temp);}}if(flag!=-1)break;}if(flag!=-1)printf("%d\n",flag);else printf("Impossible\n");}return 0;
}