p=. !probleme-de-acoperire2?P276.jpg!

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele$ '$2$':#prob2, $3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele$ '$2$':probleme-de-acoperire2#prob2, '$3$':probleme-de-acoperire3#prob3 şi '$4$':probleme-de-acoperire4#prob4 pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

h2(#prob8). Problema 8 ( _CSP 1993, Lot 2001, "Domino":http://acm.sgu.ru/problem.php?contest=0&problem=101, "The Tiling Problem":http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005_ )

bq. Se dă o tablă de dimensiuni $N x M$, din care unele pătrate sunt eliminate. Se cere să se determine o acoperire a tablei cu număr maxim de dominouri $(1 <= N, M <= 200)$. De exemplu, o tablă ce nu are nicio celulă eliminată, de $3 x 3$ pătrăţele poate fi acoperită cu cel mult $4$ dominouri care nu se suprapun. O soluţie posibilă este prezentată în a doua figură.

bq. Se dă o tablă de dimensiuni $N x M$, din care unele pătrate sunt eliminate. Se cere să se determine o acoperire a tablei cu număr maxim de dominouri $(1 <= N, M <= 200)$. De exemplu, o tablă ce nu are nicio celulă eliminată, de $3 x 3$ pătrăţele, poate fi acoperită cu cel mult $4$ dominouri care nu se suprapun. O soluţie posibilă este prezentată în a doua figură.

p=. !probleme-de-acoperire2?P281.jpg!

p=. !probleme-de-acoperire2?P282.jpg!

Acum vedem că un domino poate fi amplasat pe tablă şi el trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

Acum vedem că un domino poate fi amplasat pe tablă şi el trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de '$cuplaj maxim într-un graf bipartit$':usaco-ian-2005-divizia-gold#cover. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

p=. !probleme-de-acoperire2?P283.jpg!