Odessa restoranlarına səyahət
Odessa — çox məşhur bir şəhərdir. Ona Odessa-ana deyirlər, çünki o, müxtəlif millətlərdən olan insanlar üçün doğma evə çevrilib. Ən əsası isə, bu insanların hamısı müxtəlif mədəniyyətlərə, baxışlara və dillərə baxmayaraq, sülh və razılıq içində yaşayırlar. Buna görə də Odessada müxtəlif mədəniyyətlərin mətbəxlərini təmsil edən restoranlar mövcuddur.
Turistlər, adətən, yemək yeməyi sevirlər. Gürcü, fransız və italyan milli yeməklərini dadmaq maraqlıdır... Bunun üçün restoranlar arasında hərəkət etmək lazımdır, bu isə qiymətli vaxt tələb edir. Siz, iqtisadi proqramçı olaraq, restoranlar arasında hərəkət prosesini optimallaşdırmaq istəyirsiniz. Siz Odessa restoranlarının xəritəsini tapmısınız və indi sizdə lazım olan hər şey var.
Millətlər 1-dən K-ya qədər olan rəqəmlərlə nömrələnib. Xəritədə hər bir restoran təmsil etdiyi millətin nömrəsi ilə işarələnib. Siz müxtəlif mətbəxləri nömrələmə sırasına görə (1, 2, 3 və s.) ziyarət etməyə qərar verdiniz, hər bir millətin mətbəxini yalnız bir dəfə ziyarət etmək şərti ilə. Siz birinci mətbəxin istənilən restoranından başlaya və K-cı mətbəxin istənilən restoranında bitirə bilərsiniz. Sizi qane edəcək ən qısa yolu tapın.
Odessada küçələr ciddi şəkildə perpendikulyardır (ən azı bələdçilər belə deyir :) ), buna görə də xəritənin N×M ölçülü düzbucaqlı olduğunu və vahid kvadratlara bölündüyünü düşünəcəyik. Ümumi tərəfi olan kvadratlar arasında hərəkət etmək olar. Həmçinin, koordinatları (x_1, y_1) və (x_2, y_2) olan hüceyrələr arasındakı məsafənin |x_2-x_1|+|y_2-y_1| olduğunu qəbul edəcəyik. Nəzərə alın ki, restorana girmədən restoran olan kvadratın üstündən keçə bilərsiniz.
Giriş verilənləri
Birinci sətirdə tam ədədlər N, M, K (1 ≤ N, M ≤ 100, 1 ≤ K ≤ N×M) verilib. Növbəti N sətirdə hər biri M ədəd — bu vahid kvadratda restoranın təmsil etdiyi millətin nömrəsi (1-dən K-ya qədər) və ya 0, əgər orada restoran yoxdursa. Bütün K millətlərin restoranlarının xəritədə olduğu təmin edilir.
Çıxış verilənləri
Tək bir ədəd — ən qısa yolun uzunluğu.