Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- bool primeSieve[100000], vis[100000];
- int d[100000];
- void preprocess() {
- memset(primeSieve, true, sizeof primeSieve);
- for(int i=2; i<100000; i++) {
- if(!primeSieve[i]) continue;
- for(int j=2; i*j<100000; j++)
- primeSieve[i*j] = false;
- }
- }
- bool valid (int curN, int changedN) {
- bool ret = changedN < 100000 && changedN > 999;
- if(!ret) return ret;
- ret &= primeSieve[changedN];
- int changeCnt = 0;
- string s = to_string(curN), t = to_string(changedN);
- for(int i=0; i<4; i++) {
- changeCnt += s[i]!=t[i];
- }
- ret &= changeCnt==1;
- return ret;
- }
- int fastpow(int y) {
- return (int)pow(10, y);
- }
- void Test_Case() {
- memset(vis, false, sizeof vis);
- int n, m; cin >> n >> m;
- queue<int>q;
- q.push(n);
- d[n] = 0;
- vis[n] = 1;
- while((int)q.size()) {
- int curN = q.front(); q.pop();
- for(int i=0; i<4; i++) {
- for(int j=0; j<10; j++) {
- int changedN1 = curN+fastpow(i)*j;
- int changedN2 = curN-fastpow(i)*j;
- if(valid(curN, changedN1)) {
- if(vis[changedN1]==0) {
- q.push(changedN1);
- d[changedN1] = 1+d[curN];
- vis[changedN1] = 1;
- }
- }
- if(valid(curN, changedN2)) {
- if(vis[changedN2]==0) {
- q.push(changedN2);
- d[changedN2] = 1+d[curN];
- vis[changedN2] = 1;
- }
- }
- }
- }
- }
- cout << d[m] << "\n";
- }
- int main() {
- preprocess();
- int t; cin >> t;
- for(int i=1; i<=t; i++)
- Test_Case();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
