eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Похід по одеським ресторанам

Похід по одеським ресторанам

Ліміт часу 8 секунд
Ліміт використання пам'яті 16 MiB

Одеса – дуже знаменити місто. Його називають Одеса-мама – адже вона стала рідним будинком для людей самих різних національностей. І, що найголовніше, усі ці люди живуть у мирі та згоді, не дивлячись на різні культури, погляди, мови. І тому в Одесі є ресторани, які представляють кухні самих різних культур.

Туристи, за звичай, полюбляють поїсти. Адже цікаво спробовати і грузинську національну їжу, і французську і італьянську… Для цього потрібно переміщуватись між ресторанами, на що витрачається дорогоцінний час. Ви, як економний програміст, хочете оптимізувати процес переміщень між ресторанами. Ви знайшли карту ресторанів Одеси, і тепер у вас є усе необхідне.

Национальності пронумеровано числами від 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, К (1N, M100, 1KN×M). У наступних N рядках по M чисел – номер національності (від 1 до К), яку представляє ресторан у цьому одиничному квадраті або 0, якщо у ньому немає ресторану. Гарантується, що ресторани усіх K національностей є на карті.

Вихідні дані

Єдине число – довжина найкоротшого шляху.

Приклад

Вхідні дані #1
2 3 3
1 1 2
3 0 1
Вихідні дані #1
4
Автор Андрій Селіванов
Джерело III Відкрита Дистанційна Олімпіада 2013-2014 ім. В.Л.Дідковського