S - SnímkyČasový limit: 5s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]
ÚlohaLeká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. VstupPrvý 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:
VýstupVý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íkladVstup:7 10 .......... .?......?. .....*###. ....****.. ...#.**##. ..?....#?. .......... Výstup3 PoznámkaZo všetkých zadaných vstupov je najmenšia vzdialenosť 3 (viď obrázok). |