Programozás‎ > ‎Feladatok‎ > ‎

Sárkány-labirintus

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.

Bemenet

A 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.

Kimenet

Minden 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

Bemenet  Kimenet
2
2 3
0 2 1 0
2 -1 5
3 -1 6
4 4
0 2 3 2
-1 1 1 2
1 1 1 1
2 -1 -1 1
1 1 1 1
Case #1: Mission Impossible.
Case #2: 7


Tesztadatok

Címkék

Algoritmusok: szélességi bejárás

megoldás