III Open Distance Programming Olympiad name V.L.Didkovsky 2013-2014
Поход по одесским ресторанам
Одесса – очень знаменитый город. Её называют Одесса-мама – ведь она стала родным домом для людей самых разных национальностей. И, что самое главное, все эти люди живут в мире и согласии, несмотря на разные культуры, взгляды, языки. И поэтому в Одессе есть рестораны, представляющие кухни самых разных культур.
Туристы, конечно, любят поесть. Но интересно ведь попробовать и грузинскую национальную пищу, и французскую и итальянскую… Для этого надо перемещаться между ресторанами, на что уходит драгоценное время. Вы, как экономный программист хотите оптимизировать процесс перемещения между ресторанами. Вы нашли карту ресторанов Одессы, и теперь у вас есть всё необходимое.
Национальности пронумерованы числами от 1 до K. На карте каждый ресторан обозначены номером национальности, которую он представляет. Вы решили посетить различные кухни в порядке их нумерации (1, 2, 3 и т.д.), причем посетить кухню каждой национальности ровно один раз. Вы можете начать из любого ресторана первой кухни и закончить в любом ресторане K-й кухни. Найдите кратчайший по длине путь, который вас устроит.
В Одессе улицы строго перпендикулярны (по крайней мере так утверждают экскурсоводы :) ), поэтому будем считать, что карта – это прямоугольник N×M, разбитый на единичные квадраты. Перемещаться можно между квадратами, имеющими общую сторону. Также будем считать, что расстояние между клетками с координатами (x1, y1) и (x2, y2) равно |x2-x1|+|y2-y1|. Учтите, что вы можете проходить по квадрату с рестораном, не заходя в этот ресторан.
Input data
В первой строке заданы целые числа N, M, К (1 ≤ N, M ≤ 100, 1 ≤ K ≤ N×M). В следующих N строках по M чисел – номер национальности (от 1 до К), которую представляет ресторан в этом единичном квадрате или 0, если в нём нет ресторана. Гарантируется, что рестораны всех K национальностей есть на карте.
Output data
Единственное число – длина кратчайшего пути.
Examples
2 3 3 1 1 2 3 0 1
4