fork(1) download
copy 
  1. //...START BY DOING WHAT IS NECESSARY, THEN WHAT IS POSSIBLE AND SUDDENLY YOU ARE DOING THE IMPOSSIBLE... 
  2. #include <bits/stdc++.h>
  3. using namespace std;typedef long long ll;
  4. #define FAST_FURIER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define mk make_pair
  8. #define sorta(v)            sort(v.begin(), v.end())
  9. #define sortd(v)            sort(v.begin(), v.end(), comp)
  10. #define rep(i,a,N)          for(ll i=a;i<N;i++)
  11. #define rrep(i,a,N)         for(ll i=a;i>N;i--)
  12. #define print(v)            for(ll ite=0;ite<v.size();ite++){cout<<v[ite]<<' ';}cout<<endl;
  13. #define M 1000000007
  14. bool comp(ll x,ll y)
  15. {
  16.     return x > y;
  17. }
  18.  
  19. /*..............................code starts here........................*/
  20. // C is first won in M
  21. vector<int> adj[10];
  22. vector<int> visited(100005,false);
  23. vector<int> dist(100005,0);
  24. int n;
  25. string s;
  26. int bfs() {
  27.     queue<pair<int,int> > q;
  28.     q.push({0,0});
  29.     dist[0] = 0;
  30.     visited[0] = true;
  31.     while(!q.empty()) {
  32.         int index = q.front().first, step = q.front().second;
  33.         // cout << "index " << index << endl;
  34.         q.pop();
  35.         if(index == n-1){
  36.             break;
  37.         }
  38.         char no = s[index];
  39.         vector<int> v = adj[no-'0'];
  40.         rep(i,0,v.size()) {
  41.             if(visited[v[i]]) continue;
  42.             visited[v[i]] = true;
  43.             dist[v[i]] = step + 1;
  44.             q.push({v[i], dist[v[i]]});
  45.         }
  46.         rep(i,0,v.size()) {
  47.             if(v[i]-1>=0 and !visited[v[i]-1]){
  48.                 visited[v[i]-1] = true;
  49.                 dist[v[i]-1] = dist[v[i]] + 1;
  50.                 q.push({v[i]-1,dist[v[i]-1]});
  51.             }
  52.             if(v[i]+1 <n and !visited[v[i]+1]){
  53.                 visited[v[i]+1] = true;
  54.                 dist[v[i]+1] = dist[v[i]] + 1;
  55.                 q.push({v[i]+1, dist[v[i]+1]});
  56.             }
  57.         }
  58.     }
  59.     return dist[n-1];
  60. }
  61. void solve(){
  62.     cin >> s;
  63.     n = s.length();
  64.     rep(i,0,n){
  65.         adj[s[i]-'0'].pb(i);
  66.     }
  67.     cout << bfs() << endl;
  68. }
  69. int main() {
  70.     FAST_FURIER;
  71.     int tt=1;
  72.     // cin >> tt;
  73.     while(tt--){
  74.         solve();
  75.  
  76.     }
  77. }
  78.  
  79.  
  80.  
  81.  
  82. // g++ -std=c++17
Success #stdin #stdout 0s 4964KB
comments (?)
stdin
copy 
01234567890
stdout
copy 
1
https://ideone.com/TIZ8TF
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!