2013年8月27日

UVa 12101 - Prime Path

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define PB push_back
using namespace std;

bool np[10000];
vector<int> con[10000];

int main() {
  np[0] = np[1] = true;
  for (int i = 2; i < 10000; i++) {
    if (!np[i]) {
      for (int j = i + i; j < 10000; j += i) {
        np[j] = true;
      }
    }
  }
  for (int i = 1000; i < 10000; i++) {
    if (!np[i]) {
      for (int j = 0; j < 4; j++) {
        for (int d = !i; d < 10; d++) {
          char temp[9];
          sprintf(temp, "%d", i);
          if (temp[j] - '0' != d) {
            temp[j] = d + '0';
            int next = atoi(temp);
            if (!np[next]) {
              con[i].PB(next);
            }
          }
        }
      }
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b;
    scanf("%d%d", &a, &b);
    queue<int> q;
    q.push(a);
    bool found = false;
    int dis[10000] = {};
    while (!q.empty()) {
      a = q.front();
      int d = dis[a];
      q.pop();
      if (a == b) {
        printf("%d\n", d);
        found = true;
        break;
      }
      for (int i = 0; i < con[a].size(); i++) {
        if (!dis[con[a][i]]) {
          dis[con[a][i]] = d + 1;
          q.push(con[a][i]);
        }
      }
    }
    if (!found) {
      puts("Impossible");
    }
  }
  return 0;
}

沒有留言:

張貼留言