Az S. 105. feladat (2016. február)

S. 105. Adott egy \(\displaystyle N\times M\) (\(\displaystyle 1\le N, M\le 50\))-es térkép egy szigetvilágról legföljebb 15 szigettel. A térképen a szárazföldet `X', a mély vizet `.' és a sekély vizet `S' jelöli. Béla a téglalap alakú térkép oldalainak megfelelő négy fő irányban tud mozogni. Először ejtőernyővel érkezik egy általa választott szigetre. Egy sziget egy összefüggő szárazföld-darab, azaz olyan X-ek együttese, melyek közt el lehet jutni úgy, hogy közben csak X-re lépünk. Ezután Béla célja az összes sziget végiglátogatása. Béla nagyon jól tud sétálni, ám úszni annál kevésbé. Mély vízben képtelen úszni, így az egyetlen célja, hogy minél kevesebbszer kelljen sekély vízben úsznia. Tehát útja során minél kevesebbszer lépjen S mezőre. Tudjuk, hogy mindenképp meglátogatható az összes sziget.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, majd a következő \(\displaystyle N\) sorból a térképet. Írja a standard output első és egyetlen sorába a lehető legrövidebb összes úszás hosszát a szigetvilág minden szigetének meglátogatása közben.

Magyarázat: A felső szigetről indulva a középsőre 1 úszással, majd a jobb alsóra 2-vel el lehet jutni.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s105.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

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

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila, Mernyei Péter, Noszály Áron, Szakály Marcell.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.

A KöMaL 2016. februári informatika feladatai