【题目链接】click here~~
【题目大意】给你n,m各自是素数，求由n到m变化的步骤数，规定每一步仅仅能改变个十百千一位的数，且变化得到的每个数也为素数
【解题思路】和poj 3278类似。bfs+queue,分别枚举个十百千的每一位就能够了，只是注意个位仅仅能为奇数，且千位从1開始
代码：
#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif // C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; #define rep(i,j,k) for(int i=(int)j;i<(int)k;++i) #define per(i,j,k) for(int i=(int)j;i>(int)k;--i) #define lowbit(a) a&-a #define Max(a,b) a>b?a:b #define Min(a,b) a>b?
b:a #define mem(a,b) memset(a,b,sizeof(a)) typedef long long LL; typedef unsigned long long LLU; typedef double db; const int N=15000; const int inf=0x3f3f3f3f; int n,m,T; bool vis[N]; int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; int dir6[6][3]= {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};///六个方向 inline LL read() { int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f; } bool isPrime(int t)///素数推断 { for(int i=2; i<=sqrt(t); ++i) if(t%i==0) return false; return true; } struct node { int val,step; }; void bfs() { mem(vis,false); node a,b; a.val=n; a.step=0; queue<node >vall; vall.push(a); while(!vall.empty()){ a=vall.front(); vall.pop(); if(a.val==m){ printf("%d ",a.step); return ; } int ge=a.val%10;///枚举个位 int shi=a.val%100/10;///枚举十位 for(int i=1; i<=9; i+=2){///个位 int y=(a.val/10)*10+i; if(y!=a.val&&isPrime(y)&&!vis[y]){ b.val=y; b.step=a.step+1; vis[y]=1; vall.push(b); } } for(int i=0; i<=9; i++){///十位 int y=(a.val/100)*100+i*10+ge; if(y!=a.val&&isPrime(y)&&!vis[y]){ b.val=y; b.step=a.step+1; vis[y]=1; vall.push(b); } } for(int i=0; i<=9; i++){///百位 int y=(a.val/1000)*1000+i*100+ge+shi*10; if(y!=a.val&&isPrime(y)&&!vis[y]){ b.val=y; b.step=a.step+1; vis[y]=1; vall.push(b); } } for(int i=1; i<=9; i++){///千位 int y=a.val%1000+i*1000; if(y!=a.val&&isPrime(y)&&!vis[y]){ b.val=y; b.step=a.step+1; vis[y]=1; vall.push(b); } } } puts("Impossible"); return ; } int main() { T=read(); while(T--) { n=read(),m=read(); if(n==m) puts("0"); else bfs(); } return 0; } /* Sample Input 3 1033 8179 1373 8017 1033 1033 Sample Output 6 7 0 */