eolymp
Competitions

III Open Distance Programming Olympiad name V.L.Didkovsky 2013-2014

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

prb4545

Одесса – очень знаменитый город. Её называют Одесса-мама – ведь она стала родным домом для людей самых разных национальностей. И, что самое главное, все эти люди живут в мире и согласии, несмотря на разные культуры, взгляды, языки. И поэтому в Одессе есть рестораны, представляющие кухни самых разных культур.

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

Национальности пронумерованы числами от 1 до K. На карте каждый ресторан обозначены номером национальности, которую он представляет. Вы решили посетить различные кухни в порядке их нумерации (1, 2, 3 и т.д.), причем посетить кухню каждой национальности ровно один раз. Вы можете начать из любого ресторана первой кухни и закончить в любом ресторане K-й кухни. Найдите кратчайший по длине путь, который вас устроит.

В Одессе улицы строго перпендикулярны (по крайней мере так утверждают экскурсоводы :) ), поэтому будем считать, что карта – это прямоугольник N×M, разбитый на единичные квадраты. Перемещаться можно между квадратами, имеющими общую сторону. Также будем считать, что расстояние между клетками с координатами (x1, y1) и (x2, y2) равно |x2-x1|+|y2-y1|. Учтите, что вы можете проходить по квадрату с рестораном, не заходя в этот ресторан.

Входные данные

В первой строке заданы целые числа N, M, К (1N, M100, 1KN×M). В следующих N строках по M чисел – номер национальности (от 1 до К), которую представляет ресторан в этом единичном квадрате или 0, если в нём нет ресторана. Гарантируется, что рестораны всех K национальностей есть на карте.

Выходные данные

Единственное число – длина кратчайшего пути.

Time limit 8 seconds
Memory limit 16 MiB
Input example #1
2 3 3
1 1 2
3 0 1
Output example #1
4
Author Андрей Селиванов
Source III Открытая Дистанционная Олимпиада 2013-2014 им. В.Л.Дидковского