Az I. 378. feladat (2015. május)

I. 378. Adott egy $\displaystyle N\times M$ pixelből álló fekete-fehér kép, amelyet táblázatos elrendezésben 0 és 1 számokkal írunk le. Egy ilyen képet akkor tekintünk szépnek, ha az élszomszédos mezők közül minél több azonos. Célunk az eredeti kép szebbé alakítása bizonyos pixelek értékének megcserélésével. Egy képpont cseréje $\displaystyle Q$ forintba kerül. Az átalakított kép szépségét úgy vesszük figyelembe, hogy minden élszomszédos, különböző színű pixelpár további $\displaystyle P$ forint ,,költséget'' jelent. Keressük meg néhány adott képre azt az átalakítást, amely mellett a lehető legkisebb a $\displaystyle P+Q$ költség.

Programot nem kell beküldeni, egyedül a három, honlapunkról letölthető (in.1, in.2, in.3) képre kell három kimenetet adni (out.1, out.2, out.3). A bemenet első sorában négy egész szám áll: $\displaystyle N$, $\displaystyle M$, $\displaystyle P$, $\displaystyle Q$ -- a táblázat sorainak, oszlopainak száma, illetve a két költséget leíró paraméter. Ezután $\displaystyle N$ sor következik, mindegyikben $\displaystyle M$ karakter: a fénykép. A kimenet szintén egy $\displaystyle N\times M$-es táblázat a bemenethez hasonló formában. A feladatra nem feltétlenül kell optimális megoldást adni, mivel a feladat beküldői egymással versenyeznek: az kap 10 pontot, akinek a három bemenetre összesen a legkisebb a $\displaystyle P+Q$ költség, a többiek arányosan kevesebbet. Például a következő kép esetén:

egy lehetséges (nem feltétlenül optimális) átalakítás:

Itt $\displaystyle 6\cdot 2+3\cdot 3 =21$ forint a költség.

Beküldendő a három átalakított fénykép egy tömörített (i378.zip) állományban.

Letöltendő állományok: in.1, in.2, in.3.

(10 pont)

A beküldési határidő 2015. június 10-én LEJÁRT.

Statisztika:

6 dolgozat érkezett.
10 pontot kapott:	Gercsó Márk.
9 pontot kapott:	Kovács 246 Benedek.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.

A KöMaL 2015. májusi informatika feladatai