Nemzetközi Informatikai Diákolimpia 1992

Bonn, Németország



1. napi feladat (100 pont)
Egy tenger adatait egy NxN-es mátrixban tároljuk. A szigeteket a mátrixban '*' karakterek jelzik. E mátrix adatait kódoljuk, s a Te feladatod a kódolt adatokból az eredeti mátrix visszaállítása. A kód illusztrálására názzük a következő térképet:
 
*   * *     1 2
  * * *   * 3 1
*   *   *   1 1 1
  * * * * * 5
* *   *   * 2 1 1
      *     1
1
1
1
1
2
4 2
3
2 1
2
 

A sorok jobb oldalán lévő számok az abban a sorban található szigetek csoportjának méretét és sorrendjét mutatják. Például az első sor 1 2-je azt jelenti, hogy előbb egy 1 szigetből álló csoport, majd egy 2 szigetből álló csoport jön, s a sor többi helyén tenger van. Az oszlopok alatti számok jelentése hasonló. Például az első oszlop alatti 1 1 1 szerint három 1 szigetes csoport van.

Feladat:

Írj programot, amely a következő lépésseket ismétli mindaddig, amíg a több információs blokkot tartalmazó input állomány végére nem érünk.
  1. Olvasd be a következő információs blokkot az ASCII input állományból (E file szerkezetét az alábbi példákban lehet látni), és az adatokat jelenítsd meg a képernyőn. Minden blokk egy négyzetes mátrix sorszámával kezdődik. Ezután következnek a sorok és oszlopok kódjai. Minden sor, illetve oszlop kódja külön sorban található. A számok szóközökkel vannak elválasztva és a sort egy 0 zárja le.
  2. A kódok alapján állítsd elő a térképet ( vagy az összes térképet, ha több megoldás is létezik.) és jelenítsd meg a képernyőn.
  3. Írd ezeket a térképeket egy ASCII output állományba. A szigeteket * és egy szóköz, a tengert két szóköz jelölje. A megoldásokat üres sorok választják el egymástól. Ha nincs megoldás, a file-ba 'nincs térkép' sor kerüljön. Az egyes információs blokkok megoldásai a 'Következő probléma' szöveggel legyenek elválasztva.
  4. A mátrix mérete nem lehet kisebb, mint 1, és nem lehet nagyobb, mint 8.
Példa:
 
SZIGET.IN TERKEP.OUT
6
1 2 0
3 1 0
1 1 1 0
5 0
2 1 1 0
1 0
1 1 1 0
1 2 0
4 0
2 3 0
2 0
1 2 0
*.**..
.***.*
*.*.*. 
.*****
**.*.*
...*..
4
0
1 0
2 0
0
0
1 0
2 0
0
....
..*.
.**.
....
2
0
0
2 0
2 0
nincs térkép
2
1 0
1 0
1 0
1 0
*.
.*

.*
*.