/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 10000 vector<int>prime; bool status[MX+2]; int pl; void PrimeGenerate(int n) { int sq=sqrt(n); for(int i=3; i<=sq; i+=2) { if(!status[i]) for(int j=i*i; j<=n; j+=(i<<1)) status[j]=true; } status[0]=status[1]=true; for(int i=4;i<=n;i+=2) status[i]=true; prime.push_back(2); for(int i=3; i<=n; i+=2) if(!status[i]) prime.push_back(i); return; } int dp[MX], st, ed, taken[MX], dist[10010]; vector<int>v[10010]; int bfs(int num) { if(num==ed) return 1; dist[num]=1; queue<int>Q; Q.push(num); while(!Q.empty()) { int qq=Q.front(); Q.pop(); for(int i=0;i<v[qq].size();i++) if(!dist[v[qq][i]]) { dist[v[qq][i]]=dist[qq]+1; if(v[qq][i]==ed) return dist[v[qq][i]]; Q.push(v[qq][i]); } } return 100000; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc, kk=1, n; PrimeGenerate(MX); int loopst; pl=prime.size(); for(int i=0;i<pl;i++) if(prime[i]>999) { loopst=i; break; } for(int i=loopst;i<pl;i++) { for(int j=loopst;j<pl;j++) { int tmp=prime[i]; int tmp2=prime[j], cnt=0; while(tmp && tmp2) { if(tmp%10 != tmp2%10) cnt++; tmp/=10; tmp2/=10; } if(cnt==1) { v[prime[i]].push_back(prime[j]); } } } cin>>tc; while(tc--) { cin>>st>>ed; if(ed>st) swap(st, ed); CLR(dist); int ans=bfs(st); if(ans<100000) cout<<ans-1<<"\n"; else cout<<"Impossible\n"; } return 0; }
Friday, 27 May 2016
Prime Path (UVA 12101, SPOJ PPATH, POJ 3126, HDU 1973, UVALive 3639, Regionals 2006 >> Europe - Northwestern)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment