Programozás‎ > ‎Feladatok‎ > ‎

Kerítések

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