fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef pair<int,int> pi;
  7.  
  8. #define F first
  9. #define S second
  10. #define pb push_back
  11. #define MP make_pair
  12. #define PI 3.14
  13. #define NIL -1
  14. #define lli long long int
  15. #define MOD7 1e9+7
  16. #define MOD9 1e9+9
  17.  
  18. #define in(x) cin>>(x)
  19. #define inn(x,y) cin>>(x)>>(y)
  20.  
  21. int X8[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  22. int Y8[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  23.  
  24. int X4[4] = {-1, 0, 1, 0};
  25. int Y4[4] = {0, 1, 0, -1};
  26.  
  27. #define out(x) cout<<(x)<<"\n";
  28. #define out2(x,y) cout<<(x)<<" "<<(y)<<"\n";
  29.  
  30. inline bool isOdd(int num){
  31.     return (num & 1) ? true : false;
  32.     //returns 0 if even else return 1 for
  33. }
  34.  
  35. bool cmpVectorPair(const pair<int, int> &a, const pair<int, int> &b){
  36.     return (a.first < b.first);
  37.     //if a.first < b.first then it will sort in assending order
  38.     //if a.first > b.first then in desending order
  39. }
  40.  
  41. #define REP(iterator, starting, limit) for(int iterator = starting;  iterator < limit; iterator++)
  42. #define REPLL(iterator, starting, limit) for(lli iterator = starting;  iterator < limit; iterator++)
  43.  
  44. string s;
  45. vector<bool> visited(100005, false);
  46. vector<int> distancea(100005, 0);
  47. vector<vector<int>> edges(10, vector<int>());
  48.  
  49. int main()
  50. {   ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     cin>>s;
  53.     int n = s.size();
  54.  
  55.     REP(i, 0, n){
  56.         int intEq = s[i] - '0';
  57.         edges[intEq].push_back(i);
  58.     }
  59.  
  60.     // REP(i, 0, 10){
  61.     //     cout<<"for: "<<i<<" ";
  62.     //     for(auto x : edges[i]){
  63.     //         cout<<x<<" ";
  64.     //     }
  65.     //     cout<<"\n";
  66.     // }
  67.     queue<int> pending;
  68.     pending.push(0);
  69.     visited[0] = true;
  70.  
  71.     while(!pending.empty()){
  72.         int topIndex = pending.front();
  73.         pending.pop();
  74.  
  75.         if(topIndex == n-1)
  76.             break;
  77.  
  78.         //traverse list
  79.         int x = s[topIndex] - '0';
  80.         for(auto it : edges[x]){
  81.             if(!visited[it]){
  82.                 visited[it] = true;
  83.                 distancea[it] = distancea[topIndex] + 1;
  84.                 pending.push(it);
  85.             }
  86.         }
  87.         // go prev
  88.         if(topIndex - 1 >= 0 && !visited[topIndex - 1]){
  89.             visited[topIndex - 1] = true;
  90.             distancea[topIndex - 1] = distancea[topIndex] + 1;
  91.             pending.push(topIndex -1);
  92.         }
  93.         //go forw
  94.         if(topIndex +1 < n && !visited[topIndex + 1]){
  95.             visited[topIndex + 1] = true;
  96.             distancea[topIndex + 1] = distancea[topIndex] + 1;
  97.             pending.push(topIndex + 1);
  98.         }
  99.     }
  100.  
  101.     cout<<distancea[n-1];
  102.     return 0;
  103. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lwN9Xq
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!