Raz za mnou prisiel moj kamarat Imro a ziadal ma o radu. Zacal hrat jednu nemenovanu hru a nevedel sa pohnut z miesta. Trapil sa uz niekolko dni, tak som sa nad nim zlutoval a rozhodol som sa, ze mu pomozem. Hra, ktoru hral vyzerala celkom jednoducho. Ovladate v nej hrdinu, ktory musi prejst mapou plnou nastrah az k vytuzenemu cielu. Existuje niekolko typov nastrah a kazda zoberie nasmu hrdinovi niekolko bodov. Ak hrdina pride o vsetky body, tak umiera a hra konci. Samozrejme, nestaci prejst mapu zivy, je potrebne, aby po ceste hrdina stratil co najmenej bodov, kedze ich urcite bude potrebovat v dalsom levele. Zistil som taktiez, ze hrdina je carodejnik a dokaze sa premiestnovat podla urcitych pravidiel na rozne miesta na mape. Kazde kuzlo vsak tiez stoji nejake body. Po dlhsom hrani sa mi podarilo zostavit mapu zlozenu zo stvorcovych policok a pre kazde som zistil o kolko bodov pride hrdina, ak na neho stupi. Zistil som taktiez, ze premiestnovacie kuzla funguju nasledovne: Hrdina sa moze premiestnit na policko sumerne podla jednej osi mapy, to stoji 10 bodov alebo sucasne sumerne podla oboch osi, to stoji 20 bodov. Teda ak mapa ma rozmery 10x10 policok a hrdina je na policku [2,2], tak sa za 10 bodov moze premiestnit bud na policko [9,2] alebo na [2,9] a za 20 bodov na policko [9,9]. Bez kuziel sa moze hrdina presunut len medzi polickami susediacimi hranou. Nesmie vyjst mimo mapu. To je ale vsetko, na co som doteraz prisiel. Rad by som ale Imrovi pomohol, preto vas prosim o pomoc. Napiste mi program, ktory mi pomoze.
Uloha
Vasou ulohou je nacitat mapu a zistit, kolko minimalne bodov musi hrdina stratit, aby sa dostal k cielu.
Vstup
Prvy riadok vstupu obsahuje dve cele cisla N,M, N je pocet riadkov a M je pocet stlpcov. 1 ≤ N,M ≤ 50. Dalej nasleduje N riadkov, kazdy obsahuje M cisel oddelenych medzerami. Kazde cislo je v rozmedzi od 0 do 1000 a urcuje pocet bodov, ktore hrdina strati, ak stupi na toto policko. Dalsi riadok obsahuje styri cisla A,B,X,Y, A,B je zaciatocna pozicia hrdinu a X,Y je pozicia ciela. Predpokladajte, ze hrdina uz na zaciatocnom policku stoji, teda zacina s nulovou stratou.
Vystup
Prvy riadok vystupu obsahuje jedine cislo, minimalny pocet bodov, ktore hrdina strati.
Prikald
Vstup:
5 5
100 100 100 100 100
10 10 10 0 10
100 100 100 100 100
10 10 10 10 10
100 100 100 100 100
4 3 2 4
Vystup:
20
Vysvetlenie:
Hrdina sa pohne smerom vpravo na policko [4,4], to ho stoji 10 bodov. Potom pouzije kuzlo a presunie sa na poziciu [2,4], co ho stoji dalsich 10 bodov. To je uz ale ciel.
Problem by Samuel BWPOW KUpka
|
|