Поход по одесским ресторанам
Одесса – очень знаменитый город. Её называют Одесса-мама – ведь она стала родным домом для людей самых разных национальностей. И, что самое главное, все эти люди живут в мире и согласии, несмотря на разные культуры, взгляды, языки. И поэтому в Одессе есть рестораны, представляющие кухни самых разных культур.
Туристы, конечно, любят поесть. Но интересно ведь попробовать и грузинскую национальную пищу, и французскую и итальянскую… Для этого надо перемещаться между ресторанами, на что уходит драгоценное время. Вы, как экономный программист хотите оптимизировать процесс перемещения между ресторанами. Вы нашли карту ресторанов Одессы, и теперь у вас есть всё необходимое.
Национальности пронумерованы числами от 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 национальностей есть на карте.
Выходные данные
Единственное число – длина кратчайшего пути.