*D. Unlock*

O primă soluţie posibilă este cea de a itera pe rând prin toate cele $K$ culori şi a efectua câte o parcurgere a matricei pentru a verifica dacă celulele libere sunt conexe. Această soluţie are complexitate worst-case $O(N * M * K)$, iar date fiind limitările lui $K$, este echivalentă cu $O((N * M) ^ 2)$. Deşi la prima vedere ar părea că este puţin probabil ca atât $K$ cât şi zonele atinse de fiecare parcurgere să fie de mărime $Theta(N * M)$ simultan, există teste în care acest lucru se întâmplă, iar soluţia descrisă depăşeşte cu mult limita de timp, care, mai mult, este calibrată pentru a procesa $25$ de teste, nu unul singur.

O primă soluţie posibilă este cea de a itera pe rând prin toate cele $K$ culori şi a efectua câte o parcurgere a matricei pentru a verifica dacă celulele libere sunt conexe. Această soluţie are complexitate worst-case $O(N * M * K)$, iar date fiind limitările lui $K$, este echivalentă cu $O((N * M) ^2^)$. Deşi la prima vedere ar părea că este puţin probabil ca atât $K$ cât şi zonele atinse de fiecare parcurgere să fie de mărime $Θ(N * M)$ simultan, există teste în care acest lucru se întâmplă, iar soluţia descrisă depăşeşte cu mult limita de timp, care, mai mult, este calibrată pentru a procesa $25$ de teste, nu unul singur.

Pentru a obţine o soluţie mai rapidă, vom încerca ca pentru fiecare culoare fixată să depunem efort (i.e număr de operaţii) proporţional cu numărul total de celule de această culoare. Deoarece în total acest număr este limitat de $N * M$, complexitatea ar fi şi ea proporţională cu această valoare. Pentru a construi o asemenea soluţie, vom face pentru început nişte parcurgeri care vor identifica zonele conexe de celulele libere. Apoi, pentru fiecare culoare fixată, fie ea $C$, vom face o parcurgere pentru fiecare componentă conexă de culoare $C$ şi vom reţine cu ce zone conexe libere este vecină fiecare astfel de componentă. Dacă o anumită componentă Comp de culoare $C$ este vecină cu zonele libere $“x1, x2 .. xT”$, atunci aceste zone vor deveni conectate în momentul în care o facem pe Comp accesibilă. Astfel, pentru fiecare componentă îi putem uni vecinii cu o structură de date eficientă (de tip păduri de mulţimi disjuncte), iar la final trebuie ca toate zonele libere iniţiale să fie conexe. Pentru a justifica faptul că numărul de operaţii este proporţional cu mărimea componentelor de culoare $C$, observăm faptul că fiecare zonă liberă vecină cu o anumită componentă trebuie să fie adiacentă cu componenta respectivă pe cel puţin o latură a unei celule din componentă. Deoarece numărul de laturi al unei componente conexe este limitat de $4 * (mărimea componentei)$, rezultă că numărul maxim de vecini distincţi posibili este limitat de aceeaşi valoare.