M - MinimumČ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 ]
ÚlohaVďaka napredovaniu technológie snímania ľudského tela je dnes možné sledovať aj priebeh laparoskopickej operácie a kontrolovať jej priebeh priebežnými snímkami. Lekári univerzitnej nemocnice (na Slovensku) sú samozrejme nútení používať tieto snímky podľa možností čo najmenej, aby sa minimalizovali náklady na liečbu. U jedného pacienta potrebujú vykonať odber z nálezu-útvaru objaveného na snímke, pričom ale chcú celý priebeh dokumentovať snímkami (aby to mohli publikovať v lekárskom časopise). 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). |