Saturday, February 8, 2020

POJ.3126 Prime Path

1.Problem
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