A Sárkánykirályság léte veszélyben forog, mert kezd elfogyni az energia. A nép megmentéséhez energiát kell szerezni valahonnan. Egy ősi legenda szerint az energia forrása a Sárkány-labirintus, ami néha előbukkan a semmiből egy véletlen helyen, és egy ideig ott van, azután eltűnik. Pillanatnyilag ismert a labirintus helye. A labirintus egy téglalap alakú táblázattal írható le. Mezői vagy energiát tartalmaznak, vagy áthatolhatatlan veszélyt. A veszélyes mezőkre tilos rálépni. Ismert a labirintus bejáratának helye és a kijárat helye is. Mivel a labirintus bármelyik pillanatban eltűnhet, a lehető legkevesebb lépéssel kell átjutni rajta. A lépések élszomszédos mezőkre érkezhetnek. Ha egy energiát tartalmazó mezőre lépünk, automatikusan begyűjtjükaz ott található energiamennyiséget. Egy mezőn csak egyszere lehet energiát felvenni. Szeretnénk gyorsan áthaladni a labirintuson, de közben a maximális energiamennyiség begyűjtése a célunk.
FeladatÍrjunk programot, ami kiszámolja a minimális lépésszámmal begyűjthető maximális energiamennyiséget.
BemenetA bemenet első sorában a tesztesetek 1 <= T <= 30 száma található. Minden teszteset a labirintus N és M méretével kezdődik (1 <= N, M <= 100). Ezután a start és a cél koordinátái jönnek sor - oszlop sorrendben, 0-tól (N-1)-ig és 0-tól (M-1)-ig számozva. Végül N sorban, soronként M oszlopban a labirintus leírása következik, ahol a pozitív számok az adott mezőn begyűjthető energia mennyiségét írják le, a -1 pedig veszélyes mezőt jelez, amire tilos rálépni.
KimenetMinden kimenetre adjuk meg a minimális lépésszámmal megszerezhető maximális energia értékét, vagy írjuk ki a "Mission Impossible." szöveget, ha nincs út a start és a cél között.
Példa
Tesztadatok
CímkékA feladat forrása: google Code Jam China New Grand Test 2014 Round B
Algoritmusok: szélességi bejárás
megoldás |
Programozás > Feladatok >