fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool prime[10001];
  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<10000;i++)
  11.     {
  12.         if(prime[i] == true)
  13.         {
  14.             for(int p=2*i;p<10000;p+=i)
  15.             {
  16.                 prime[p] = false;
  17.             }
  18.         }
  19.     }
  20. }
  21. bool is_connected(int a,int b)
  22. {
  23.     string x = to_string(a);
  24.     string y = to_string(b);
  25.     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]);
  26. }
  27. void generate_graph(int src,int des)
  28. {
  29.     for(int i=src;i<=des;i++)
  30.     {
  31.         if(prime[i] == true)
  32.         {
  33.             for(int j=i+1;j<=des;j++)
  34.             {
  35.                 if(prime[j] == true && is_connected(i,j))
  36.                 {
  37.                     adj[i].push_back(j);
  38.                     adj[j].push_back(i);
  39.                 }
  40.             }
  41.         }
  42.     }
  43. }
  44. int bfs(int src,int dest)
  45. {
  46.     queue<int> q;
  47.     memset(level,0,sizeof(level));
  48.     memset(visited,false,sizeof(visited));
  49.     level[src] = 0;
  50.     q.push(src);
  51.     visited[src] = true;
  52.     while(!q.empty())
  53.     {
  54.         int top = q.front();
  55.         q.pop();
  56.         for(int i=0;i<adj[top].size();i++)
  57.         {
  58.             if(visited[adj[top][i]] == false)
  59.             {
  60.                 q.push(adj[top][i]);
  61.                 visited[adj[top][i]] = true;
  62.                 level[adj[top][i]] = level[top] + 1;
  63.                 if(adj[top][i] == dest)
  64.                     return level[adj[top][i]];
  65.             }
  66.         }
  67.     }
  68.     return -1;
  69. }
  70. int main()
  71. {
  72.     soE();
  73.     int t;
  74.     cin >> t;
  75.     while(t--)
  76.     {
  77.         int a,b;
  78.         cin >> a >> b;
  79.         generate_graph(a,b);
  80.         int ans = bfs(a,b);
  81.         if(a == b)
  82.             cout << "0\n";
  83.         else if(ans != -1)
  84.             cout << ans << "\n";
  85.         else
  86.             cout << "Impossible\n";
  87.     }
  88. }
Success #stdin #stdout 0.13s 4216KB
comments (?)
stdin
copy 
3
1033 8179
1373 8017
1033 1033
stdout
copy 
5
4
0
https://ideone.com/xDRo7p
language:
C++ (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!