POJ 3126 Prime Path

問題

素数が2つ与えられる。素数のいずれかの桁の数字を一つ書き換えて別の素数に変える操作を、与えられるひとつ目の素数から始めて、ふたつ目の素数に到達するまで行う。最短の操作回数を求めよ。ただし与えられる素数はともに4桁の素数で、経由する素数も4桁であること。

やりかた

ひとつ目の素数から初めてふたつ目の素数を幅優先探索で探していけばいい。
ある桁の数字だけ書き換える操作は文字列であれば楽だけど、そうしたらTLEしたので数字のまま行う必要あり。

以下ソース。

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

int main(int argc, char **argv){
  int N; cin >> N;
  while(N--){
    int s, t; cin >> s >> t;
    
    queue<int> Q;
    Q.push(s);
    int dist[10000];
    fill(dist, dist + 10000, -1);
    dist[s] = 0;
    while(!Q.empty()){
      int a = Q.front(); Q.pop();

      if(a == t) break;
      
      for(int base = 1; base <= 1000; base *= 10){//各桁を書き換えてみる
	for(int digit = 0; digit < 10; digit++){
	  int x = a;
	  x = x - x % (base * 10) + x % base;
	  x += base * digit;
	  if(x >= 1000 && prime(x) && dist[x] == -1){//4桁の素数でまだ調べていなければキューに入れる
	    dist[x] = dist[a] + 1;
	    Q.push(x);
	  }
	}
      }
    }
    if(dist[t] == -1) cout << "Impossible" << endl;
    else cout << dist[t] << endl;
  }
  return 0;
}

例えばある数字xのある位だけを0にしたければ以下のようする。

int base;//100の位だけ0にしたければ100にする
x = x - x % (base * 10) + x % base;