NézetNyomtat

Át a labirintuson (Megoldás)
Címkék > Feladat

Át a labirintuson

A tökéletes labirintusok a következő tulajdonságokkal írhatók le:
  • bármely két "szoba"/csomópont között van út
  • bármely két "szoba"/csomópont között pontosan egy út van
Labirintusok bejárására több módszer ismert.

A-módszer

Legrövidebb út.

B-módszer

Bal kézzel mindig fogjuk a falat.

Feladat

Írj programot, ami megadja, hogy lehet eljutni a bejárattól a kijáratig.

Bemenet

A bemenet első sora a labirintus méretét adja meg, ez mindig páratlan szám, $3\le N \le 255$. Ezután $N+2$ sorban $N+2$ karakter következik, a labirintus leírása.
'#': fal
' ': út
A bejárat mindig a második sor első mezője, kezdetben jobbra nézünk. A kijárat mindig az utolsó előtti sor utolsó mezője, erre kell rálépni.

Kimenet

A kimenetben kétféle módon adjuk meg az utat. Egyrészt lépéssorozattal (E- előre, J - jobbra, B- balra), másrészt a labirintusban '.' karakterrel jelölve, merre jártunk. A kimenet első sora a lépések száma (a fordulásokat is lépésnek számolva), a második sor a lépések listája nagybetűs karakterekkel kódolva, a következő $N+2$ sor pedig a bejárás ábrája, a példában látható módon.

Példa

lab.txtlab.kiAlab.kiB
5
#######
      #
### ###
#     #
# # # #
# # #  
#######
14
EEEJEEBEEJEEBE
#######
....  #
###.###
#  ...#
# # #.#
# # #..
#######
20
EEEEEJJEEBEEBEEJEEBE
#######
......#
###.###
#  ...#
# # #.#
# # #..
#######

Tesztadatok