一道经典的BFS
用四个for搜索四位就行了，只要能推出怎么只变4位中的一位就很水了
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 using namespace std; 8 int t; 9 int n,m; 10 int book[100001]={0};//记录有没有搜过 11 struct node//x表示现在的数，step表示当前的次数 12 { 13 int x; 14 int step; 15 }; 16 queue<node> q;//广搜队列 17 bool zyc_pd(int x)//判断素数 18 { 19 if(x==0||x==1)return false; 20 else if(x==2||x==3)return true; 21 else 22 { 23 for(int i=2;i<=(int)sqrt(x);i++) 24 { 25 if(x%i==0)return false; 26 } 27 return true; 28 } 29 30 } 31 void bfs() 32 { 33 int x1,step1,i; 34 while(!q.empty()) 35 { 36 node tmp; 37 tmp=q.front(); 38 q.pop(); 39 x1=tmp.x;//赋初始值 40 step1=tmp.step;//赋初始值 41 //cout<<x1<<endl; 42 if(x1==m)//如果搜到结果，输出 43 { 44 cout<<step1<<endl; 45 return; 46 } 47 for(i=1;i<=9;i+=2)//个位，从一到九的奇数（因为是素数） 48 { 49 int yy=x1/10*10+i;//去掉个位再加上搜到的个位 50 if(yy!=x1&&!book[yy]&&zyc_pd(yy))//不能与上一步数一样+不能重复搜+是素数 51 { 52 book[yy]=1;//标记为搜过 53 node temp; 54 temp.x=yy;//制为当前的值 55 temp.step=step1+1;//搜索次数加1 56 q.push(temp); 57 } 58 } 59 for(i=0;i<=9;i++)//十位同理 60 { 61 int yy=x1/100*100+i*10+x1%10; 62 if(yy!=x1&&!book[yy]&&zyc_pd(yy)) 63 { 64 book[yy]=1; 65 node temp; 66 temp.x=yy; 67 temp.step=step1+1; 68 q.push(temp); 69 } 70 } 71 for(i=0;i<=9;i++)//百位同理 72 { 73 int yy=x1/1000*1000+i*100+x1%100; 74 if(yy!=x1&&!book[yy]&&zyc_pd(yy)) 75 { 76 book[yy]=1; 77 node temp; 78 temp.x=yy; 79 temp.step=step1+1; 80 q.push(temp); 81 } 82 } 83 for(i=1;i<=9;i++)//千位 84 { 85 int yy=i*1000+x1%1000;//只换千位 86 if(yy!=x1&&!book[yy]&&zyc_pd(yy)) 87 { 88 book[yy]=1; 89 node temp; 90 temp.x=yy; 91 temp.step=step1+1; 92 q.push(temp); 93 } 94 } 95 } 96 cout<<"Impossible"<<endl;//如果搜不到输出Impossible 97 return; 98 } 99 int main() 100 { 101 cin>>t; 102 while(t--) 103 { 104 while(!q.empty())q.pop();//清空队列 105 cin>>n>>m; 106 memset(book,0,sizeof(book));//初始化book数组 107 book[n]=1;//把book【n】制为搜过 108 node tmp; 109 tmp.x=n;//当前的数为n 110 tmp.step=0;//当前步数为0 111 q.push(tmp); 112 bfs(); 113 } 114 return 0; 115 }
请各位大佬斧正（反正我不认识斧正是什么意思）