Chef and Digit Jumps
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves games! But he likes to invent his own. Now he plays game "Digit Jump". Chef has sequence of digits S1, S2,..., SN,. He is staying in the first digit (S1) and want to reach the last digit (SN) in the minimal number of jumps.
While staying in some digit x with index i (digit Si) Chef can jump into digits with indices i - 1 (Si-1) and i + 1 (Si+1) but he can't jump out from sequence. Or he can jump into any digit with the same value x.
Help Chef to find the minimal number of jumps he need to reach digit SN from digit S1.
Input contains a single line consist of string S of length N- the sequence of digits.
In a single line print single integer - the minimal number of jumps he needs.
- 1 ≤ N ≤ 10^5
- Each symbol of S is a digit from 0 to 9.
Input: 01234567890 Output: 1 Input: 012134444444443 Output: 4
In the first case Chef can directly jump from the first digit (it is 0) to the last (as it is also 0).
In the second case Chef should jump in such sequence (the number of digits from 1: 1-2-4-5-15).
|Tags||berezin, bfs, dijkstra, easy, june14|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.