Похід по одеським ресторанам
Одеса – дуже знаменити місто. Його називають Одеса-мама – адже вона стала рідним будинком для людей самих різних національностей. І, що найголовніше, усі ці люди живуть у мирі та згоді, не дивлячись на різні культури, погляди, мови. І тому в Одесі є ресторани, які представляють кухні самих різних культур.
Туристи, за звичай, полюбляють поїсти. Адже цікаво спробовати і грузинську національну їжу, і французську і італьянську… Для цього потрібно переміщуватись між ресторанами, на що витрачається дорогоцінний час. Ви, як економний програміст, хочете оптимізувати процес переміщень між ресторанами. Ви знайшли карту ресторанів Одеси, і тепер у вас є усе необхідне.
Национальності пронумеровано числами від 1 до K. На карті кожен ресторан позначено номером національності, яку він представляє. Ви вирішили відвідати різні кухні у порядку їх нумерації (1, 2, 3 і т.д.), причому відвідати кухню кожної національності рівно один раз. Ви можете почати з довільного ресторану першої кухні і завершити у довільному ресторані K-ї кухні. Знайдіть найкоротший по довжині шлях, який вас влаштує.
В Одесі вулиці строго перпендикулярні (у всякому випадку так стверджують екскурсоводи :) ), тому будемо вважати, що карта – це прямокутник N×M, розбитий на одиничні квадрати. Переміщуватись можна між квадратами, які мають спільну сторону. Також будемо вважати, що відстань між клітинками з координатами (x_1, y_1) та (x_2, y_2) дорівнює |x_2-x_1|+|y_2-y_1|. Врахуйте, що ви можете проходити по квадрату з рестораном, не заходячи у цей ресторан.
Вхідні дані
У першому рядку задано цілі числа N, M, К (1 ≤ N, M ≤ 100, 1 ≤ K ≤ N×M). У наступних N рядках по M чисел – номер національності (від 1 до К), яку представляє ресторан у цьому одиничному квадраті або 0, якщо у ньому немає ресторану. Гарантується, що ресторани усіх K національностей є на карті.
Вихідні дані
Єдине число – довжина найкоротшого шляху.