Solving safe breaking

See more:

optimization

DynamicMethod

, +

0 down vote
favorite
This question was recently ask in a contest which is now over, but they don't share the editorials with us and this question is stuck in my mind and i am not able to get the answer in optimal way, anybody please explain the proper approach for this is very helpful-:(And if possible please explain like a editorial THNAKS)

"Satish has a combination safe that consists of multiple rotating dials that are placed next to each other. Each dial is etched with digits 0 through 9, in order. At any stage, exactly one of the digits on each dial is visible. The string formed by concatenating the visible digits of each dial is termed as the current combination. The visible digit on a dial can be changed by rotating the dial up or down. Rotating the dial up increases the digit by 1 i.e. 0 to 1, 1 to 2, and so on. The digits on a dial wrap around so a 9 is followed by 0. Rotating the dial down changes the digit in the reverse direction. We can rotate multiple adjacent dials at the same time. That is, in a single step we can take an arbitrary number of consecutive dials, and rotate all of them one step in the same direction (i.e., either all of them down, or all of them up). Satish is given the current combination (C) and the required combination (R) that unlocks the safe. Write a program to determine the minimum number of steps required to open the safe.
Example: Consider the case where C is “986” and R is “007”. This can be solved in two steps as follows:
Step-1: rotate all 3 dials up. “986” to “097”
Step-2: rotate 2nd dial up. “097” to “007”,

ex. 9 2 7 7 8 2 4 3 2 8 to 5 4 5 7 4 9 4 6 2 9 need 16 steps."

What I have tried:

I tried to solve it by brute force but it give TLE .