GRAPHS/prime_path_spoj.cpp at master · dbarnwal/GRAPHS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// PUSH YOUR LIMITS.!!

#include<bits/stdc++.h>
using namespace std;

typedef long double ld;
#define int long long

#define RAGE ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for(i=0; i <n; i++)
#define repv(i,k,n) for(i=k; i<n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define endl '\n'
int mod = 1e9+7;
int power(int x,int n)
{   if(n==0)    return 1;
    if(n==1)    return x%mod;
    if(n%2==0)  {   int y = power(x,n/2)%mod;return (y*y)%mod;}
    if(n&1)     {   int y = power(x,n-1);return (x%mod * y%mod)%mod;}
    return 0;
}
int dx[]={-1 , 0 , 1 , 0};
int dy[]={ 0 , -1, 0 , 1};
const int maxn = 100005;
//  ------------------------------------------------------------------
vector<int> vis(maxn);
vector<int> dist(maxn);
vector<int> adj[maxn];
vector<int> primes;

bool is_prime(int n)
{
    for(int i=2; i*i<=n; i++)
    {   if(n%i==0)
            return false;
    }
    return true;
}

bool is_valid(int a ,int b)
{
    int cnt=0;
    while(a>0)
    {
        if(a%10 != b%10)
            cnt++;
        a/=10 , b/=10;
    }
    if(cnt==1)
        return true;
    return false;
}
void build_graph()
{
    int i,j;
    for(i=1000; i<=9999; i++)
    {   if(is_prime(i))
            primes.pb(i);
    }

    for(i=0; i<sz(primes); i++)
    {
        for(j=i+1; j<sz(primes); j++)
        {
            int a = primes[i];
            int b = primes[j];

            if(is_valid(a,b))
            {
                adj[a].pb(b);
                adj[b].pb(a);
            }
        }
    }
}

void bfs(int n)
{
    queue<int> q;
    vis[n] = 1;
    dist[n] = 0;
    q.push(n);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        for(int x:adj[v])
        {
            if(!vis[x])
            {
                q.push(x);
                dist[x] = dist[v] + 1;
                vis[x]  = 1;
            }
        }
    }
}

void solve()
{
    int n,i,j,k,m;
    vis.assign(maxn , 0);
    dist.assign(maxn , -1);

    cin>>n>>m;
    bfs(n);

    if(dist[m]==-1)
        cout<<"Impossible"<<endl;
    else
        cout<<dist[m]<<endl;
}
signed main()
{
    RAGE;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif


    int t=1;
    cin>>t;
    build_graph();
    while(t--)
        solve();

    #ifndef ONLINE_JUDGE
        cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
    #endif

    return 0;
}