Z - Zombiechod

Neohrozený hrdina Arnie prežíva zombie apokalypsu. Práve zachytil volanie o pomoc a chcel by sa vydať naprieč spustošeným mestom ku zdroju tohto signálu. Niektoré oblasti sú ale stále napadnuté nemŕtvymi a ak sa rozhodne vojsť, musí sa s nimi popasovať. To mu zaberie toľko času, ako prejdenie K políčok
Vedeli by ste mu pomôcť nájsť takú trasu, aby sa k signálu dostal čo najskôr?
Mesto má tvar dvojrozmernej mriežky so základňou v ľavom hornom rohu a zdrojom signálu v pravom dolnom. Obe oblasti sú bezpečné. Arnie sa z oblasti môže pohnúť na ľubovoľnú zo štyroch susedných.

Úloha

Pre daný popis mesta zistite dľžku najkratšej trasy zo základne k signálu

Vstup

V prvom riadku súboru sa nachádzajú rozmery mesta M,N a číslo K

Nasleduje M riadkov s N znakmi popisujúcimi jednotlivé oblasti

• # znamená oblasť so zombie
• . znamená bezpežnú oblasť

1 ≤ M,N ≤ 100
0 ≤ K ≤ 100

Výstup

Výstupom programu je odpoveď na samostatnom riadku.

Príklad

Vstup:

10 10 4
.#...#....
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#..
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#.#
...#...#..

Výstup:

26