From CEOIWiki

July 12-19 Košice, Slovakia Task: alliances Language: Hungarian

---

[edit] Szövetség

Van egy méretű téglalap alakú sziget mezőre osztva. Néhány közülük lakatlan, a többieken laknak. Egy-egy mezőn a lakók tündérek, emberek, törpék vagy hobbitok. Két mező akkor szomszédos, ha van közös oldala. A lakók biztonságuk érdekében szövetséget kötnek szomszédjaikkal. A szövetség két szomszédos mező lakói között kölcsönös. Az egyes lakóknak meghatározott számú szövetségesre van szükségük.

• A tündéreknek (elves) pontosan egy kell.
• Az embereknek (humans) kettő kell, de nem lehetnek a mező két szemközti oldalán.
• A törpéknek (dwarves) három kell.
• A hobbitoknak (hobbits) négy kell.

A sziget szélén lévő mezőkre is teljesülni kell a követelményeknek. Tehát a szélén lévő hobbitoknak, vagy a sarokban lévő törpéknek nem lehet kívánt számú szövetségese.

[edit] Feladat

Írj programot, amely adott szigetre eldönti, hogy mindenkinek lehet-e kívánt számú szövetségese! Ha lehet, akkor meg is kell adni minden mezőre a lehetséges szövetségeseit. Több megoldás esetén bármelyik megadható.

[edit] Bemenet

Az első sorban a sziget méretét megadó R és C egész szám van. A következő R sor írja le a szigetet. Minden sorban C, szóközökkel elválasztott, 0 és 4 közötti egész szám van, amelyek jelentése a következő:

• 0 lakatlan mező,
• 1 tündérek lakta mező,
• 2 emberek lakta mező,
• 3 törpék lakta mező.
• 4 hobbitok lakta mező.

Megjegyzés: Minden mezőre megadott szám a bemenetben megegyezik a szükséges szövetségesek számával.

[edit] Korlátok

.

55 pont szerezhető azokra a bemenetekre, ahol . További 15 szerezhető azokra, ahol .

További 10 szerezhető azon esetekre, ahol csak emberek és lakatlan mezők vannak. (Ez nem része az 55 pontos esetnek.)

[edit] Kimenet

Ha nincs megoldás, akkor az "Impossible!" szöveget kell kiírni (idézőjelek nélkül). Ha van megoldás, akkor a következő formában kell kiírni: Minden mezőt egy -as karakter-mátrix írjon le! A lakatlan mezők esetén minden karakter a pont (.) legyen! A lakott mezők középső karaktere az O (nagy O) legyen, ami magát a mezőt jelöli! A szövetséges szomszédhoz az X, a többi helyre a . karaktert kell írni!

Az alábbi ábrán látható az egyes mező típusok összes lehetséges szövetséges ábrázolása.

[edit] Példák

input:

3 4
2 3 2 0
3 4 3 0
2 3 3 1

output:

............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............

input:

1 2
2 1

output:

Impossible!