== include(page="template/taskheader" task_id="pixels") ==
Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuală să fie cât mai mare. Pentru a face asta trebuie să ştiţi 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere $A{~ij~}$ pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere $B{~ij~}$ pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii $C{~ijk~}$ care trebuie plătit dacă sunt coloraţi diferit.
Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuală să fie cât mai mare. Pentru a face asta trebuie să ştiţi 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere $A{~ij~}$ pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere $B{~ij~}$ pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii $C{~ijk~}$ care trebuie *plătit* dacă sunt coloraţi diferit.
Costul plăcerii este dat pentru fiecare pixel şi pentru fiecare 4 direcţii. Cu alte cuvinte, pentru un anumit pixel la coordonate $(i, j)$, $C{~ij0~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i - 1, j)$ sunt coloraţi diferit, $C{~ij1~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j + 1)$ sunt coloraţi diferit, $C{~ij2~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i + 1, j)$ sunt coloraţi diferit, şi $C{~ij3~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j - 1)$ sunt coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu $C{~110~}$ va fi întotdeauna 0. $C{~ij0~}$ şi $C{~(i-1)j2~}$ vor fi întotdeauna la fel, şi aşa mai departe (costul pentru fiecare pereche este simetric).
Voi trebuie să maximizaţi plăcerea totală, adică: * suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu $C{~110~}$ va fi întotdeauna 0. $C{~ij0~}$ şi $C{~i-1j2~}$ vor fi întotdeauna la fel, şi aşa mai departe (costul pentru fiecare pereche este simetric).
Voi trebuie să maximizaţi plăcerea totală, adică: *suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.
Baftă!
h2. Date de intrare
