fork download
copy 
  1. from collections import deque
  2.  
  3. s = raw_input()
  4.  
  5. lst = [int(i) for i in s ]
  6. n = len(s)
  7. visited = [ 0 for i in xrange(n) ]
  8. jumps = [10000 for i in xrange(n) ]
  9.  
  10. biglst = [[] for i in xrange(10)]
  11.  
  12. for i in xrange(n):
  13.     biglst[lst[i]].append(i)
  14.  
  15. jumps[0] = 0
  16.  
  17. queue = deque([0])
  18.  
  19. #print biglst
  20.  
  21. while(1):
  22.  
  23.     elem = queue.popleft()
  24.     flag = 0
  25.  
  26.     if(elem<len(s)-1):
  27.         if(visited[elem] == 0 and jumps[elem+1] > jumps[elem]+1):
  28.             jumps[elem+1] = jumps[elem] + 1
  29.             queue.append(elem+1)
  30.  
  31.     if(elem>0):
  32.         if(visited[elem] == 0 and jumps[elem-1] > jumps[elem]+1):
  33.             jumps[elem-1] = jumps[elem] + 1
  34.             queue.append(elem-1)
  35.     #print biglst[lst[elem]]
  36.     if(len(biglst[lst[elem]]) > 1):
  37.         for i in biglst[lst[elem]]:        
  38.             if(i != elem and visited[i] == 0 and jumps[i] > jumps[elem]+1):
  39.                 jumps[i] = jumps[elem] + 1
  40.                 queue.append(i)
  41.  
  42.     visited[elem] = 1;
  43.     if(visited[len(s)-1] == 1):
  44.         break
  45.  
  46.     #print lst
  47.     #print jumps
  48.  
  49. print jumps[len(s)-1]
Success #stdin #stdout 0.02s 8432KB
comments (?)
stdin
copy 
012134444444443
stdout
copy 
4
https://ideone.com/atXseg
language:
Python (cpython 2.7.16)
created:
9 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!