1033The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
1733
3733
3739
3779
8779
8179
Input
#include<stdio.h> #include<string.h> #include<queue> using namespace std; # define r 11311 int b[11111]; struct $ { int e,s; } q,z; void eilish() { memset(b,0,sizeof b); b[1]=1; for(int i=2; i<r; i++) { if(!b[i]) { for(int j=2; j*i<r; j++) b[i*j]=1; } } } int by(int f,int l) { int v[r]; int t; memset(v,0,sizeof v); queue<$>p; q.s=0,q.e=f; v[f]=1; p.push(q); while(!p.empty()) { q=p.front(); p.pop(); if(q.e==l) return q.s; int a[5]; a[1]=q.e/1000; a[2]=q.e/100%10; a[3]=q.e/10%10; a[4]=q.e%10; for(int i=1; i<=4; i++) { int m=a[i]; for(int j=0; j<=9; j++) { if(a[i]!=j) { a[i]=j; t=a[1]*1000+a[2]*100+a[3]*10+a[4]; } if(t>=1000&&t<=9999&&!v[t]&&!b[t]) { z.e=t,z.s=q.s+1; p.push(z); v[t]=1; } } a[i]=m; } } return -1; } int main() { int n,g,h; eilish(); scanf("%d",&n); while(n--) { scanf("%d%d",&g,&h); if(by(g,h)==-1) printf("Impossible\n"); else printf("%d\n",by(g,h)); } return 0; }
原文：https://www.cnblogs.com/R-I-P/p/12952875.html
