Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2016. december 4.

2016. december 4. 10:10 – 2016. december 4. 15:10

RoboBot

A feladatod, hogy felprogramozz egy robotot úgy, hogy megtalálja az 'E'-vel jelölt célmezőt egy 6 × 6-os labirintusban. A robot az 'S' karakterrel jelölt mezőről indul. A rács bejárása során a robot 4 irányban tud mozogni: észak, kelet, dél és nyugat felé (átlósan soha). A labirintus tartalmaz még három darab, 1 és 6 közötti méretű falat is.

A startmezőtől a célmezőig vezető legrövidebb utak egyikét kell megtalálnod. Csak szomszédos cellák közötti mozgások megengedettek; a szomszédos azt jelenti, hogy a celláknak van egy közös oldaluk és nincsenek elválasztva egymástól egy fallal. A rácsot elhagyni nem szabad.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset öt sorból áll. Az első sorban a startmező oszlop- és sorszáma, a második sorban pedig a célmező oszlop- és sorszáma szerepel. A harmadik, negyedik és ötödik sor a három fal helyzetét adja meg. Egy fal helyzetét vízszintes fal esetén a bal végpontjának, majd a jobb végpontjának a pozíciójával, függőleges fal esetén pedig a felső végpontjának, majd az alsó végpontjának a pozíciójával adjuk meg. Egy falvégpont pozícióját a végpontnak a rács bal oldalától mért távolságával, majd a rács felső oldalától mért távolságával írjuk le.

Feltételezheted, hogy a falak nem metszik egymást, de érintkezhetnek egy cella valamelyik sarkában, valamint azt is, hogy a falak végpontjai a rácson vannak. Továbbá mindig lesz legalább egy érvényes útvonal a startmezőtől a célmezőig. A példa bemenet a fenti ábrán látható labirintust írja le.

Az utolsó tesztesetet egy olyan sor követi, amely két nullát tartalmaz.

A kimenet specifikációja

Minden tesztesetre a startmezőtől a célmezőig vezető legrövidebb út leírását kell a kimenetre írni egy sorban. A leírásnak az egyes mozgások irányát kell megadnia ('N'-nel a felfelé, 'E'-vel a jobbra, 'S'-sel a lefelé, 'W'-vel pedig a balra irányt jelölve).

Előfordulhat, hogy egynél több legrövidebb út is létezik, ebben az esetben bármelyik megadható.

Példa bemenet

  1. 1 6
  2. 2 6
  3. 0 0 1 0
  4. 1 5 1 6
  5. 1 5 3 5
  6. 0 0
letöltés szöveges állományként

A példa bemenethez tartozó kimenet

  1. NEEESWW
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.