My code gives WA. I don’t understand what can possibly be wrong, all seems right. Can someone pls look into it…
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
void path(int a , int b , vvi &G)
{
int d1[4] , d2[4];
d1[3] = a%10; d2[3] = b%10;
d1[2] = (a%100 - a%10)/10; d2[2] = (b%100 - b%10)/10;
d1[1] = (a%1000 - a%100)/100; d2[1] = (b%1000 - b%100)/100;
d1[0] = (a-a%1000)/1000; d2[0] = (b-b%1000)/1000;
int fal = 0;
if(d1[0] != d2[0])
{
fal++;
if(fal==2)
return;
}
if(d1[1] != d2[1])
{
fal++;
if(fal==2)
return;
}
if(d1[2] != d2[2])
{
fal++;
if(fal==2)
return;
}
if(d1[3] != d2[3])
{
fal++;
if(fal==2)
return;
}
G[a].push_back(b);
G[b].push_back(a);
}
void calcPrime(int start , int finish , vi &v)
{
for(int i=start ; i<=finish ; i++)
{
int flag = 1;
for(int j=2 ; j<i/2 ; j++)
{
if(i%j == 0)
{
flag = 0;
break;
}
}
if(flag)
v.push_back(i);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b;
cin>>a>>b;
if(a==b)
{
cout<<"0"<<endl;
continue;
}
if(a>b)
swap(a,b);
vi v;
vvi G(b+1);
calcPrime(a,b,v);
for(int i=0 ; i<v.size()-1 ; i++)
{
for(int j=i+1 ; j<v.size() ; j++)
{
path(v[i] , v[j] , G);
}
}
vector<int> vis(b+1,-1);
queue<int> Q;
Q.push(a);
vis[a] = 0;
while(!Q.empty())
{
int i = Q.front();
Q.pop();
for(auto it = G[i].begin() ; it != G[i].end() ; ++it)
{
if(vis[*it] == -1)
{
vis[*it] = 1+vis[i];
Q.push(*it);
}
}
}
if(vis[b] == -1)
cout<<"Impossible";
else
cout<<vis[b];
}
}