http://poj.org/problem?id=3126
2.Idea
Sieve of Eratosthenes
3.Source
bool isPrime[10000];
bool visited[10000];
int n;
int s, t;
vector<int> GetNei(int cur)
{
vector<int> ans;
for (int i = 0; i < 10; i++) {
int tmp = cur - cur % 10 + i;
if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);
tmp = cur - cur % 100 + cur % 10 + 10 * i;
if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);
tmp = cur - cur % 1000 + cur % 100 + 100 * i;
if (tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);
tmp = cur % 1000 + 1000 * i;
if (i > 0 && tmp != cur && isPrime[tmp] && !visited[tmp]) ans.push_back(tmp);
}
return ans;
}
int solve()
{
for (int i = 0; i < 10000; i++) isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < 10000; i++) {
if (isPrime[i]) {
for (int j = 2 * i; j < 10000; j += i) {
isPrime[j] = false;
}
}
}
cin >> n;
while (n--) {
memset(visited, 0, sizeof visited);
cin >> s >> t;
queue<pair<int, int>> q;
q.push(make_pair(s, 0));
while (!q.empty()) {
int cur = q.front().first, d = q.front().second; q.pop();
if (cur == t) {
cout << d << endl;
break;
}
//cout << cur << endl;
visited[cur] = true;
vector<int> neibors = GetNei(cur);
for (int i = 0; i < neibors.size(); i++) {
q.push(make_pair(neibors[i], d + 1));
}
}
}
}
int main()
{
solve();
return 0;
}
No comments:
Post a Comment