Advertisement
Josif_tepe

Untitled

Oct 23rd, 2024
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. bool is_palindrome(int x) {
  8.     string s = "";
  9.     while(x > 0) {
  10.         int digit = x % 10;
  11.         s += (digit + '0');
  12.         x /= 10;
  13.     }
  14.     int i = 0, j = s.size() - 1;
  15.     while(i < j) {
  16.         if(s[i] != s[j]) {
  17.             return false;
  18.         }
  19.         i++;
  20.         j--;
  21.     }
  22.     return true;
  23. }
  24. int main() {
  25.     vector<int> palindromes;
  26.     for(int i = 1; i <= 100000; i++) {
  27.         if(is_palindrome(i)) {
  28.             palindromes.push_back(i);
  29.         }
  30.     }
  31.    
  32.     int S, E;
  33.     cin >> S >> E;
  34.    
  35.    
  36.     vector<bool> visited(100000, false);
  37.     visited[S] = true;
  38.    
  39.     queue<int> q;
  40.     q.push(S);
  41.     q.push(0);
  42.     while(!q.empty()) {
  43.         int number = q.front();
  44.         q.pop();
  45.         int dist = q.front();
  46.         q.pop();
  47.        
  48.         if(number == E) {
  49.             cout << dist << endl;
  50.             return 0;
  51.         }
  52.         for(int i = 0; i < palindromes.size(); i++) {
  53.             int palindrome = palindromes[i];
  54.             if(palindrome < number and palindrome + number <= E) {
  55.                 if(!visited[palindrome + number]) {
  56.                     visited[palindrome + number] = true;
  57.                     q.push(palindrome + number);
  58.                     q.push(dist + 1);
  59.                 }
  60.             }
  61.         }
  62.     }
  63.  
  64.    
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement