Az I. 367. feladat (2015. február)

I. 367. Egy $\displaystyle M\times N$ ($\displaystyle 5\le M, N\le 100$) négyzetből álló négyzetháló egyes négyzeteiben átlósan egy tükröt helyeztünk el, amelynek mindkét oldala tökéletesen visszaveri a fényt. A tükrök a négyzetek középpontja körül könnyen elfordulhatnak. A fény egy időegység alatt egy egységnyi (a négyzet oldalhosszának megfelelő) utat tesz meg. A fénysugár a négyzetháló oldalára merőlegesen lép be, valamely négyzet oldalfelező pontján át. Minden pillanatban, amikor a fénysugár a négyzetháló egy négyzetének oldalához ér, a tükrök 90 fokkal elfordulnak.

A bemeneti fájl első sorában a sorok, majd az oszlopok száma olvasható. A második sor adja meg, hogy milyen irányból (b, j, f, l), hányadik egységben (fentről lefele és balról jobbra számozunk) lép be a rendszerbe a fény. Az alatta levő $\displaystyle M$ sor mindegyikében pontosan $\displaystyle N$ karakter van. A szóköz karakter (a mintán o) jelöli azokat az egységeket, ahol nincs tükör, a \ és / karakterek pedig a tükröket, valamint azok kezdeti állapotát mutatják.

A kimeneti fájl első sorában a kilépésig eltelt idő, a második sorában pedig - a bemenet második sorával egyező formában - a kilépési hely olvasható. Ha a fény nem lép ki a rendszerből, az első sorba a -1 érték kerüljön, a második pedig maradjon üresen.

A program első parancssori argumentuma a bemeneti fájl neve, a második pedig a kimeneti fájl neve legyen.

Beküldendő egy tömörített i367.zip állományban a program forráskódja (i367.pas, i367.cpp, ...), valamint a program rövid dokumentációja (i367.pdf), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2015. március 10-én LEJÁRT.

A feladatot a kitűzéskor nem gondoltuk különösebben nehéznek. Ennek ellenére nemhogy tökéletes megoldást nem adott be senki, de az elérhető pontszám felét is kevesen érték el.

A feladat érdekes részét a forgó tükrök jelentették. Fel lehetett volna ismerni, hogy bemeneti cellában lévő tükör az alapállapothoz képest elfordul. Ettől a cellától számítva a páros lépésben elérhető cellákban elfordított tükrökkel lehet dolgozni, a többi cella esetén pedig az alapállapottal. Ha valaki ezt felismeri, nem kell foglalkoznia a tükrök forgatásával.

A legtöbb beküldő érdemben foglalkozott a rendszerből ki nem lépő fénysugárral. Olexó Gergely állapította meg - helyesen -, hogy ilyen helyzet nem állhat elő. (Az előző bekezdésben foglaltak alapján ez könnyen belátható.)

Azt hihetnénk, hogy a hibás megoldások a feladat félreértelmezésén alapultak. Azonban több esetben is előfordult, hogy adott tesztesetre legalább 6, de volt, hogy 10 különböző kimenet is született.

A tesztesetek közül a 0., 1., 2., 3. bizonyos állapotok kezelését vizsgálják, a 4., 5., 6., 7. esetek véletlenszerűek: i367teszt.zip

Statisztika:

11 dolgozat érkezett.
8 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2015. februári informatika feladatai