Pokoli útvesztő

Bár nem olvasható ki egyértelműen az Isteni színjáték című remekműből, de Dante Alighierit, az itáliai reneszánsz nagy költőfejedelmét nemcsak Vergilius kísérte el pokolbéli útjára, hanem Jack, a félkarú rabló is. Szükségük is volt rá, hiszen – aki még nem ismerné, annak eláruljuk, hogy – a Pokol egy rettentően zegzugos, kisze-kusza útvonalakkal teli, téglalap alapú labirintus – bár ezt maga Dante sem ismerte fel annak idején. Jack azonban, aki szinte a fél életét a Pokolban töltötte, megfigyelte, hogy nem is olyan nehéz közlekedni benne, mivel a pokolbéli utak nem tartalmaznak kört, a Pokol bármelyik két pontja között pontosan egy út vezet. Ezért aztán, ha egyetlen megmaradt kezét mindvégig a falhoz érinti, akkor a labirintus bármelyik pontjából el tud jutni bármelyik másikba anélkül, hogy eltévedne. Jack a Pokol bejáratánál várta Dantéékat – igen, annál, amelynek kapujára a „Ki itt belépsz, hagyj fel minden reménnyel” szöveg van felírva –, hogy vezetésével eljussanak a kijáratig.

Írjon programot, amely az egyetlen parancssori argumentumaként megadott szöveges állományból labirintusok adatait olvassa be! Egy labirintust leíró blokk a következőképpen épül fel: az első sor két egész számot tartalmaz, a labirintus téglalapjának hoszúságát (h) és szélességét (sz), ahol 3 ≤ h ≤ 40 és 3 ≤ sz ≤ 40. A következő h sor mindegyikében egy sz hosszúságú sztring szerepel. A labirintus sorait és oszlopait egyaránt 0-tól indexeljük. Az i-edik sztring (0 ≤ i ≤ h – 1) a labirintus i-edik sorát írja le: 'X' (nagy X) karakterek szerepelnek ott, ahol fal van, '.' (pont) karakterek pedig ott, ahol út van a labirintusban. A labirintus 0-s és (h – 1)-es indexű sorában pontosan egy cella tartalmaz '.' karaktert (utat), a 0-s indexű sorban lévő a labirintus bejáratát, a (h – 1)-es indexű sorban lévő pedig a kijáratát jelzi. Feltételezve, hogy Dante, Vergilius és Jack a bejárattól indulnak, és Jack mindvégig a jobb kezével követi a labirintus falát, egyvégtében rajta tartva azon a tenyerét, a program írja a standard kimenetre a kijáratig tartó útjuk során érintett cellák koordinátáit „(x,y)” alakban, soronként egy-egy koordinátapárt írva a kimenetre! Az első koordinátának a bejárat, az utolsónak a kijárat koordinátájának kell lennie, ez utóbbi után a program írjon ki egy üres sort is a standard kimenetre! A feldolgozandó labirintusok végét egy-egy 0-s érték jelzi a hossszúság és szélesség adatainak a helyén, ha ezt olvassa a program, akkor fejezze be a működését!

Példa állomány (sample.txt)

1. 9 9
2. XXXX.XXXX
3. X.....X.X
4. X.XXX.X.X
5. X..X....X
6. XX.XXXX.X
7. X..X.X..X
8. XXXX.X.XX
9. X.......X
10. XXXX.XXXX
11. 0 0

letöltés szöveges állományként

Parancssori argumentumok

1. sample.txt

letöltés szöveges állományként

A futtatás eredménye a standard kimeneten

1. (0,4)
2. (1,4)
3. (1,3)
4. (1,2)
5. (1,1)
6. (2,1)
7. (3,1)
8. (3,2)
9. (4,2)
10. (5,2)
11. (5,1)
12. (5,2)
13. (4,2)
14. (3,2)
15. (3,1)
16. (2,1)
17. (1,1)
18. (1,2)
19. (1,3)
20. (1,4)
21. (1,5)
22. (2,5)
23. (3,5)
24. (3,4)
25. (3,5)
26. (3,6)
27. (3,7)
28. (4,7)
29. (5,7)
30. (5,6)
31. (6,6)
32. (7,6)
33. (7,5)
34. (7,4)
35. (6,4)
36. (5,4)
37. (6,4)
38. (7,4)
39. (7,3)
40. (7,2)
41. (7,1)
42. (7,2)
43. (7,3)
44. (7,4)
45. (8,4)

letöltés szöveges állományként