P1949 [NOI2001] The Clever Typist

Alan is a typist in a confidential department. She now receives a task: she needs to enter several hundred passwords, each of fixed length $6$, within one day. Of course, she wants the total number of keystrokes during input to be as few as possible. Unfortunately, for confidentiality reasons, the keyboard used to enter passwords is specially designed. There are no numeric keys, only the following six keys: `swap0`, `swap1`, `up`, `down`, `left`, `right`. To explain the functions of these $6$ keys, we first number the $6$ positions in the input area from left to right as $1,2,3,4,5,6$. The functions of each key are listed below: - `swap0`: Pressing `swap0` keeps the cursor position unchanged and swaps the digit at the cursor with the digit at position $1$ (the leftmost digit) in the input area. If the cursor is already at position $1$, then after pressing `swap0` the digits in the input area remain unchanged. - `swap1`: Pressing `swap1` keeps the cursor position unchanged and swaps the digit at the cursor with the digit at position $6$ (the sixth digit from the left) in the input area. If the cursor is already at position $6$, then after pressing `swap1` the digits in the input area remain unchanged. - `up`: Pressing `up` keeps the cursor position unchanged and increases the digit at the cursor by $1$ (unless the digit is $9$). For example, if the digit at the cursor is $2$, after pressing `up`, it becomes $3$; if the digit at the cursor is $9$, after pressing `up`, it remains unchanged, and the cursor position also remains unchanged. - `down`: Pressing `down` keeps the cursor position unchanged and decreases the digit at the cursor by $1$ (unless the digit is $0$). If the digit at the cursor is $0$, after pressing `down`, it remains unchanged, and the cursor position also remains unchanged. - `left`: Pressing `left` moves the cursor one position to the left. If the cursor is already at position $1$ (the first position from the left), the cursor does not move. - `right`: Pressing `right` moves the cursor one position to the right. If the cursor is already at position $6$ (the sixth position from the left), the cursor does not move. To make such a keyboard useful, before each password is entered, a random initial password of length $6$ will appear in the input area, and the cursor will be fixed at position $1$. By cleverly using the six special keys above, the target password can be obtained, and at that time the cursor is allowed to stay at any position. Now Alan needs your help. Write a program to compute the minimum number of keystrokes required to enter one password.

A single line containing two numbers of length $6$: the first is the initial password, and the second is the target password, separated by a single space.

A single line containing a positive integer, the minimum number of keystrokes required.

Translated by ChatGPT 5