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.

Írjunk programot, ami kiszámolja a minimális lépésszámmal begyűjthető maximális energiamennyiséget.

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.

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.

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

A feladat forrása: google Code Jam China New Grand Test 2014 Round B

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

megoldás