János gazda kicsit túlzásba vitte a kerítésépítést a földjén, ezért egy kisebb labirintus jött létre. Szerencsére a labirintus olyan, hogy bármelyik mezőjéről van kivezető út. Azt is tudjuk, hogy a külső kerítés pontosan két helyen hiányzik, tehát két kijárat van.
Feladat
Írjunk programot, ami megadja az a minimális lépésszámot, amivel garantálható, hogy kijutunk a labirintusból, bárhonnan is induljunk.
Bemenet
A bemenet első sora a labirintus méreteit adja meg (1<=W<=38, 1<=H<=100). A következő 2*H+1 sorban a labirintus leírása következik, a példának megfelelő formátumban.
Kimenet
Az egyetlen sorba azt a minimális lépésszámot kell írni, ahány lépésben (vagy kevesebbel) bármelyik mezőről kijuthatunk a labirintusból.
Példa
Bemenet |
Kimenet |
5 3
+-+-+-+-+-+
| |
+-+ +-+ + +
| | | |
+ +-+-+ + +
| | |
+-+ +-+-+-+
|
9
|
Tesztadatok
Címkék
A feladat forrása: USACO training material, Overfencing
Algoritmusok:
megoldás |