fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool prime[10000001];
  4. vector<int> adj[10001];
  5. int level[10001];
  6. bool visited[10001];
  7. void soE()
  8. {
  9.     memset(prime,true,sizeof(prime));
  10.     for(int i=2;i*i<=9999;i++)
  11.     {
  12.         if(prime[i] == true)
  13.         {
  14.             for(int p=i*i;p<=9999;p+=i)
  15.                 prime[p] = false;
  16.         }
  17.     }
  18. }
  19. /*bool is_connected(int a,int b)
  20. {
  21.     string x = to_string(a);
  22.     string y = to_string(b);
  23.     if(x.length() == 1)
  24.     return (x[0]!=y[0]&&x[1]==y[1]&&x[2]==y[2]&&x[3]==y[3]) || (x[0]==y[0]&&x[1]!=y[1]&&x[2]==y[2]&&x[3]==y[3]) || (x[0]==y[0]&&x[1]==y[1]&&x[2]!=y[2]&&x[3]==y[3]) || (x[0]=y[0]&&x[1]==y[1]&&x[2]==y[2]&&x[3]!=y[3]);
  25. }*/
  26. void generate_graph()
  27. {
  28.     for(int i=1000;i<=9999;i++)
  29.     {
  30.         if(prime[i] == true)
  31.         {
  32.             for(int j=1000;j<=9999;j++)
  33.             {
  34.                 if(prime[j] == true)
  35.                 {
  36.                      vector <int> temp;
  37.                      int val=i,val1=j;
  38.                      while(val>0)
  39.                     {
  40.                         int x=val%10;
  41.                         int y=val1%10;
  42.                         temp.push_back(abs(x-y));
  43.                         val/=10;
  44.                         val1/=10;
  45.                     }
  46.                     sort(temp.begin(),temp.end());
  47.                     if(temp[0]==0&&temp[1]==0&&temp[2]==0&&temp[3]!=0)
  48.                     {
  49.                         adj[i].push_back(j);
  50.                         adj[j].push_back(i);
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }
  57. int bfs(int src,int dest)
  58. {
  59.     queue<int> q;
  60.     memset(level,0,sizeof(level));
  61.     memset(visited,false,sizeof(visited));
  62.     level[src] = 0;
  63.     q.push(src);
  64.     visited[src] = true;
  65.     while(!q.empty())
  66.     {
  67.         int top = q.front();
  68.         q.pop();
  69.         for(int i=0;i<adj[top].size();i++)
  70.         {
  71.             if(visited[adj[top][i]] == false)
  72.             {
  73.                 q.push(adj[top][i]);
  74.                 visited[adj[top][i]] = true;
  75.                 level[adj[top][i]] = level[top] + 1;
  76.                 if(adj[top][i] == dest)
  77.                     return level[adj[top][i]];
  78.             }
  79.         }
  80.     }
  81.     return -1;
  82. }
  83. int main()
  84. {
  85.     soE();
  86.     generate_graph();
  87.     int t;
  88.     cin >> t;
  89.     while(t--)
  90.     {
  91.         int a,b;
  92.         cin >> a >> b;
  93.         int ans = bfs(a,b);
  94.         if(a == b)
  95.             cout << "0\n";
  96.         else if(ans != -1)
  97.             cout << ans << "\n";
  98.         else
  99.             cout << "Impossible\n";
  100.     }
  101. }
Success #stdin #stdout 0.13s 13764KB
comments (?)
stdin
copy 
3
1033 8179
1373 8017
1033 1033
stdout
copy 
6
7
0
https://ideone.com/oWHW9J
problem PPATH, based on SPOJ submission 25978934 (CPP14), 2020-05-15 07:30:45
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!