Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00018A

Zidine

Tijekom razgledavanja dubrovačkih zidina, Tomislav je uočio tajni prolaz. Prolaskom kroz njega, našao se u pravokutnoj prostoriji. Na zidu je uočio tlocrt, a čim mu se približio, čuo je kako se vrata u prolazu kojim je došao zatvaraju. Uskoro je uočio i slabo vidljiv natpis:
Putniče! Nalaziš se u Sobi ključeva. Kako bi otključao Tajna vrata i izašao iz Sobe, moraš sakupiti odreñeni broj ključeva. Svi se ključevi nalaze u ovoj prostoriji i do svih je moguće doći. Na tlocrtu su položaji svih ključeva označeni slovom 'K''.


Označena je i tvoja pozicija – potraži na tlocrtu slovo 'X'. Svi zidovi označeni su znakom '#'. Prazna mjesta na karti označena su točkom ('.'). Tajna vrata su jedini izlaz iz prostorije. Sretno!


Kako Tomislav mora uskoro stići na natjecanje, zanima ga koji je najbrži način da sakupi točno K ključeva.


Tlocrt prostorije sastoji se od N redaka, svaki sa po M stupaca. Tomislav se po prostoriji kreće samo u četiri glavna smjera – gore, dolje, lijevo i desno. Tlocrt prostorije uvijek će imati zidove na rubovima, tj. neće biti moguće izaći iz prostorije (osim korištenjem Tajnih vrata, koja nisu označena na tlocrtu). Prostorija može imati i pregrade (zidove) u unutrašnjosti. U prostoriji će se nalaziti najviše 8 ključeva.


Input
- prirodni broj N (1 ≤ N ≤ 30), broj redaka tlocrta;
- prirodni broj M (1 ≤ M ≤ 30), broj stupaca tlocrta;
- prirodni broj K (1 ≤ K ≤ 8), broj ključeva koje je potrebno sakupiti;
- N redaka, u svakom po M znakova, tlocrt prostorije.

Output- cijeli broj S, najmanji broj koraka koje Tomislav mora napraviti kako bi sakupio K ključeva.


Input :
6
10
2
##########
#.X.....K#
#.....K..#
#........#
#K.......#
##########
Output:
8

Objašnjenje:

Tomislav može sakupiti 2 ključa ako prvo ode 4 polja udesno, zatim 1 prema dolje, pa 2 udesno, pa 1 prema gore. Ako bi prvo otišao do njemu najbližeg (donjeg lijevog) ključa, tada bi ukupan put bio veći, jer bi do njega napravio 4 koraka, a ostali ključevi su od donjeg lijevog ključa udaljeni 7 i 10 koraka.



Input:
6
10
2
##########
#.X#....K#
##.#.K#..#
#..####..#
#K.......#
##########
Output:
14

Objašnjenje:

U nekim primjerima zidovi mogu biti i unutar prostorije. Sada mu je najbrže pokupiti prvo donji lijevi ključ (4 koraka), a zatim gornji desni (10 koraka), jer je udaljenost do srednjeg ključa sada veća.


Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.