S - Snímky

Časový limit: 5s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Lekári univerzitnej nemocnice chcú zaznamenať priebeh odberu laparoskopickou cestou z tkaniva priebežnými snímkami vďaka novému rádiologickému zariadeniu s vysokým rozlíšením, aby ho mohli publikovať v prestížnom medicínskom časopise. U jedného pacienta potrebujú vykonať odber z nálezu-objaveného útvaru. Ponúka sa im viacero možných vstupov, potrebovali by zistiť koľko najmenej snímok musia urobiť, ak chcú zaznamenať pohyby operatívneho nástroja v maximálnom rozlíšení snímacieho prístroja. (Keďže snímacie zariadenie je rastrové, pohyb nástroja je možný v jednom z ôsmich smerov.)
Pomôžte im napísať program, ktorý nájde najmenší počet snímok potrebných na zaznamenanie pohybov lekárskeho nástroja v tele človeka na odber tkaniva z nálezu, ak lekári určili niekoľko možných vstupov.

Vstup

Prvý riadok vstupu obsahuje dve celé čísla 1 ≤ N, M ≤ 100, rozmery snímky. Nasleduje N riadkov obsahujúcich M znakov popisujúcich jeden riadok snímky s nasledovným významom:

'.' prázdne políčko
'?' možný vstup
'#' prekážka (kosť, vnútorný orgán)
'*' nález

Môžete predpokladať, že vstup je korektný (neobsahuje iné znaky, obsahuje po aspoň jednom znaku '?' aj '*')

Výstup

Výstup obsahuje jediný riadok s jedným nezáporným celým číslom, najmenšou vzdialenosťou. Ak pohyb zo žiadneho vstupu k nálezu nie je možný, tak vypíšte nulu.

Príklad

Vstup:

7 10
..........
.?......?.
.....*###.
....****..
...#.**##.
..?....#?.
..........

Výstup

Poznámka

Zo všetkých zadaných vstupov je najmenšia vzdialenosť 3 (viď obrázok).

21 Domáce 2