자물쇠에는 \(0\)부터 \(9\)까지를 표시하는 숫자 바퀴 4개가 일렬로 있어 항상 네 자리 숫자(앞자리가 \(0\)일 수 있음)를 나타낸다.

한 번의 조작으로 바퀴 하나를 골라 위 또는 아래로 한 칸 돌릴 수 있다. 즉 그 자리의 숫자를 \(+1\) 또는 \(-1\) 한다. 단, \(9\)에서 위로 돌리면 \(0\)이 되고, \(0\)에서 아래로 돌리면 \(9\)가 된다.

현재 상태 \(S\)에서 목표 상태 \(T\)로 만들고 싶다. 그런데 걸리는 상태가 \(K\)개 주어지며, 조작 도중 자물쇠가 이 상태들 중 하나가 되면 잠겨버린다(시작 상태가 걸리는 상태이면 처음부터 잠겨 아무 것도 할 수 없다).

목표 상태에 도달하기 위한 최소 조작 횟수를 구하여라. 도달할 수 없으면 \(-1\)을 출력한다.

• \(0 \le K \le 10000\)
• \(S\), \(T\), 걸리는 상태는 모두 네 자리 숫자 문자열(\(0000\) ~ \(9999\))이다.
• 걸리는 상태는 서로 다르다.

첫 줄에 시작 상태 \(S\)와 목표 상태 \(T\)가 공백으로 주어진다(각각 네 자리 숫자 문자열).

둘째 줄에 걸리는 상태의 개수 \(K\)가 주어진다.

이어서 \(K\)개의 줄에 걸쳐 각 걸리는 상태(네 자리 숫자 문자열)가 주어진다.

최소 조작 횟수를 출력하고, 도달할 수 없으면 \(-1\)을 출력한다.

riseoj 작성

출처 Original