UVa12101

UVa12101
素数表からグラフ作ってBFS

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

#include <cstdio>

using namespace std;

void make_prime(bool p[], const int size) {

  fill(p, p + size, true);
  p[0] = p[1] = false;
  for (int i = 2; i * i < size; ++i) {
    for (int j = 2; i * j < size; ++j) {
      p[i * j] = false;
    }
  }
  
  return ;
}

const int P = 10000;
static bool g[P][P];

int main(void) {
  
  bool prime[P];
  make_prime(prime, P);

  int p[P], size = 0;
  for (int i = 0; i < P; ++i) {
    if (prime[i]) p[size++] = i;
  }

  for (int i = 0; i < size; ++i) {
    for (int j = 0;j < size; ++j) {
      int a = p[i];
      int b = p[j];
      if (a < 1000) continue;
      if (b < 1000) continue;
      char s[5], t[5];      
      sprintf(s, "%04d", a);
      sprintf(t, "%04d", b);      
      int diff = 0;
      for (int k = 0; k < 4; ++k) {
        diff += t[k] != s[k];
      }
      if (diff == 1) g[a][b] = true;
    }
  }

  int tc = 0;
  cin >> tc;
  while (tc--) {
    string s, t;
    queue<int> q;
    set<int> vis;
    map<int, int> cost;

    cin >> s >> t;
    int src = atoi(s.c_str());
    int dst = atoi(t.c_str());

    cost[src] = 0;
    vis.insert(src);
    for (q.push(src); q.size(); q.pop()) {
      int a = q.front();
      for (int i = 0; i < size; ++i) {
        int b = p[i];
        if (!g[a][b]) continue;
        if (vis.count(b)) continue;
        vis.insert(b);
        cost[b] = cost[a] + 1;
        q.push(b);
      }
    }

    if (vis.count(dst)) cout << cost[dst] <<  endl; 
    else cout << "Impossible" << endl; 
  }

  return 0;
}