problem s prekrivanjem likov

zivjo!

imam eno vprasanje, in sicer me zanima, na kaksen nacin bi se bilo najpametneje lotit resevanje sledecega problema:

imam neko polje tocno dolocenih dimenzij x in y, z vrednostmi ali 0 ali 1:

0 0 1
0 1 1
1 1 0

pac, nek vzorec. potem pa imam n nekih oblik, katerih dimenzje so manjse ali enake polju, npr (recimo temu prvi lik):

0 1
1 1

ali (recimo temu drugi lik):

1 1 1

ali (recimo temu tretji lik):

0 0 1
0 0 1
1 1 1

etc. te oblike je treba aplicirati na glavno polje, in sicer tako, da ce je v liku vrednost 0, se v polju vrednost ne spremeni, ce pa je v liku vrednost 1, se vrednost polja v glavnem liku zamenja, 0 -> 1 in 1 -> 0. paziti je potrebno tudi na dimenzije lika, prvi lik lahko na 4 razlicne lokacije apliciram na glavno polje, drugi lik 3x, 3. lik pa le 1x. naj ponazorim na primeru:

iz glavnega polja, kot je zgoraj in zgornjih dveh likov bi dobil npr:

apliciranje prvega lika v spodnji levi del glavnega polja:

0 0 1
0 0 1
0 0 0

apliciranje drugega lika na spodnjo vrstico:

0 0 1
0 0 1
1 1 1

in zadnji lik na edino mozno mesto:

0 0 0
0 0 0
0 0 0

stvar je v tem, da v koncni fazi zelim ugotoviti, na katera mesta naj apliciram like, da iz zacetnega polozaja glavnega polja dobim samo vrednosti 0 (ali 1, odvisno od v zacetku podane zahteve). zacetno polje je lahko razlicnih oblik, dimenzije so podane vnaprej. stevilo likov je razlicno, podano vnaprej, znane so tudi oblike likov, kot je prikazano zgoraj. za samo pripravo likov in glavnega polja meni ni potrebno skrbeti, polje in liki so pripravljeni tako, da na koncu _vedno_ dobim ali samoe vrednosti 0 ali 1. se enkrat. vseeno je, na kateri polozaj dam kak lik (vendar mora biti ves lik znotraj polja, ne sme nic ven gledat), vazno je le, da je rezultat taksen, kot ze omenjeno. vmes pravilnosti ne morem preverjati, moznih pa je lahko vcasih tudi vec resitev, zanima pa me samo ena (prva )

zelel sem poskusiti z brute force metodo, se pravi poskusiti z vsemi moznimi kombinacijami likov in na koncu uporabniku izpisati, na katera mesta je potrebno uvrstiti kak lik, da je glavno polje ali polno ali pa prazno. problem pa je v tem, da se mi je zataknilo pri dejanski izvedbi. razmisljal sem o rekurzivni funkciji, samo nimam pojma, kako bi to izvedel. rabil bi naceloma le kak namig, brco v pravo smer, napotek na literaturo, s katero bi si lahko pomagal pri tem specificnem problemu, etc.

zadevo sicer pisem v php-ju, vendar to niti ni toliko pomembno, zanima me zgolj postopek, kako naj se zadeve lotim. najlepsa vam dala

Lahko si zastaviš požrešen algoritem. Rečeš, da moraš v vsakem koraku povečati število ničel / enic na sliki in tako hitro zreduciraš delo tvoji brute force metodi. Sicer ne vem če se to da s tvojimi liki (če obstaja lik, ki ti obrne le eno cifro - ki ti lahko ostane ko apliciraš nekaj iteracij te požrešne metode). Če se ne da bi lahko ročno skombiniral še nekaj likov, ki bi to znali narediti. Npr:

Če zaporedoma na sliki apliciraš tvoj lik #2 in #3:

1 1 1

in

0 0 1
0 0 1
1 1 1

je to isto kot če bi apliciral enega od spodnjih (pač odvisno kje uporabiš lik #2)

1 1 0 | 0 0 1 | 0 0 1
0 0 1 | 1 1 0 | 0 0 1
1 1 1 | 1 1 1 | 0 0 0

Pri tem si označiš zadnji lik (ki je recimo zanimiv) kot lik #101, ga dodaš programu (da ga bo znal uporabiti) in si zapomniš kako si ga naredil. Če ta lik zaslediš v rešitvi ga pač zamenjaš z zaporedjem #2, #3 na pravilnih koordinatah.

Zdaj tudi ne rabiš požrešne rekurzije ampak lahko to spišeš v eni iteraciji. Pač poskusiš aplicirati vse like na vseh možnih koordinatah in takoj ko najdeš eno kombinacijo, ki ti izboljša sliko jo obdržiš (sliko), si zapomniš kombinacijo in začneš z naslednjo iteracijo. Predpostavka tu je nadvse pomembna - vedno mora obstajati nek lik, ki ti na neki poziciji izboljša trenutno sliko.

Zmisliš si nek pameten način, da svojo mxn matriko zapišeš kot (m*n)x1, recimo iz

11
00

pridelaš

1100

Svoje vzorce potem gor popaš, kot da bi računal z bitnimi nizi, recimo

matrika XOR vzorec

Malo si poglej še redukcijske algoritme (po domače, kako iz danega niza priti do željenega z najmanj osnovnimi operacijami) za boolovo algebro.

@gundolf: ja, vsak lik le enkrat, najbolje po zaporedju, kakor so podani, ni pa to nujno.
@owca: hvala, si mi dal nekaj idej za nadaljnje resevanje in mozganje. hvala! v primeru problemov se definitivno se oglasim nazaj
zaenkrat pa hvala obema!
p.s.: seveda se ne branim dodatnih nasvetov, ce ima se kdo kaj za dodat