Об'їзд у Великій Манілі

Метро Маніла сьогодні складається з п'яти окружних доріг, розташованих у вигляді концентричних півкіл, а шоста дорога незабаром буде збудована і з'єднає північ і південь. Із центру (Маніла) виходить десять радіальних доріг, які з'єднують внутрішні та зовнішні частини Метро Маніли.

Рисунок 1 Ідеальна мережа доріг Великої Маніли

У цій задачі потрібно знайти найкоротшу відстань від точки A до точки B. Кожна точка визначається перетином окружної та радіальної дороги, позначених як (\textbf{C\#}, \textbf{R\#}), а центр — як (\textbf{C0}, \textbf{R0}).

Для розрахунків уважаємо, що відстань кожного відрізка радіальної дороги дорівнює $1$ одиниці, а дуга окружної дороги має довжину, що дорівнює її номеру. Наприклад, відстань від (\textbf{C1}, \textbf{R3}) до (\textbf{C2}, \textbf{R3}) дорівнює $1$ одиниці, а відстань від (\textbf{C3}, \textbf{R1}) до (\textbf{C3}, \textbf{R2}) — $3$ одиниці. Найкоротша відстань від (\textbf{C1}, \textbf{R2}) до (\textbf{C5}, \textbf{R1}) дорівнює $5$ одиниць (див. затемнений шлях). Для цієї задачі вважаємо, що рух по $\text{C6}$ дозволений.

Однак за новою системою кодування транспортних засобів не можна використовувати радіальну дорогу, номер якої збігається з останньою цифрою номерного знака транспортного засобу. Наприклад, транспортний засіб з номером ABC-123 не може використовувати $\text{R3}$. Крім того, окружні дороги (окрім $\text{C6}$) також мають обмеження: номери, що завершуються на $1$ і $2$, не допускаються на $\text{C1}$; $3$ і $4$ — на $\text{C2}$; $5$ і $6$ — на $\text{C3}$; $7$ і $8$ — на $\text{C4}$; $9$ і $0$ — на $\text{C5}$. Таким чином, найкоротший шлях з (\textbf{C1}, \textbf{R2}) до (\textbf{C5}, \textbf{R1}) для транспортного засобу з номером ABC-123 дорівнює $5$ одиниць; для $\text{CBA-321}$ — $9$ одиниць. Зауважте, що можуть бути випадки, коли дістатися до пункту призначення неможливо.