Source Code

• Source Code

  #include <iostream>
  #include <cstring>
  #include <queue>
  using namespace std;
  #define MAX 9999
  int prime[MAX+1];
  int visit[MAX+1];
  int st,ed;
  int bas[4]= {1,10,100,1000};
  void shai()
  {
      for(int i=2; i<=MAX; ++i) prime[i]=1;
      int t;
      for(int i=2; i<=MAX/2; ++i)
      {
          t=2*i;
          while(t<=MAX)
          {
              prime[t]=0;
              t+=i;
          }
      }
  }
  
  void bfs()
  {
      fill(visit,visit+9999,0);
      queue<int> q;
      queue<int> qs;
      int t,ts;
      int n,ns;
      ts=0;
      t=st;
      q.push(t);visit[t]=1;
      qs.push(ts);
      int num,i,j;
      while(1)
      {
          t=q.front();q.pop();
          ts=qs.front();qs.pop();
          if(t==ed)
          {
              cout<<ts<<endl;
              return;
          }
          for(i=0; i<4; ++i)
              for(j=0; j<10; ++j)
              {
                  if(i==3&&j==0) continue;
                  num=t/bas[i]%10;
                  if(num!=j)
                  {
                      n=t-num*bas[i]+j*bas[i];
                      ns=ts+1;
                      if(!visit[n]&&prime[n]) {q.push(n);visit[n]=1;qs.push(ns);}
                  }
              }
      }
  
  }
  int main()
  {
      shai();
      int cas;
      cin>>cas;
      while(cas--)
      {
          cin>>st>>ed;
          bfs();
      }
  }