Solutia problemei Marceland

Numim componenta 4-conexa o multime maximala de celule, pentru care, oricum am alege doua celule din aceasta multime, exista un drum intre acestea mergand doar prin celule care nu contin # (nu sunt blocate) si trecand dintr-o celula doar intr-o alta celula care are o latura comuna cu ea.
Problema se reduce la determinarea tuturor componentelor 4-conexe si adaugarea convenabila a fantanilor: pentru o componenta care contine cel putin un Marcel, dar nu contine nicio fantana, se cauta o celula cu nisip din aceasta componenta si se inlocuieste cu o fantana, daca nu exista o celula cu nisip disponibila (componenta conexa contine doar M) atunci nu avem solutie.

In functie de metoda de determinare a componentelor 4-conexe se pot obtine punctaje diferite:

• Pentru N=1, componentele conexe sunt determinate de intervale compacte maximale care nu contin #. Putem astfel determina componentele conexe printr-o simpla parcurgere a vectorului, numarand fiecare tip de celula intalnita in componenta curenta.
• Pentru N=2, consideram mai intai intervalele compacte maximale de pe cele doua linii care nu contin # (asemanator cu situatia anterioara). Pentru a determina componentele conexe, sortam aceste intervale dupa capatul stanga, apoi le parcurgem in aceasta ordine mentinand care este cel mai mare capat dreapta al unui interval deja procesat. Componentele conexe sunt gasite de la stanga la dreapta astfel: daca acest capat dreapta maxim este cel putin egal cu capatul stanga al intervalului curent, atunci intervalul curent apartine ultimei componente conexe determinate si actualizam informatiile pentru aceasta componenta, altfel incepe o componenta noua, iar pentru componenta anterioara detinem deja informatiile finale.
• Pe cazul general, putem aplica o parcurgere in latime (BFS) din celule care contin M, astfel: cautam o celula care contine M si nu a fost vizitate, folosind parcurgerea in latime marcam ca vizitate toate celulele la care are acces acest M (determinam astfel componenta sa 4-conexa) si numaram cate celule de tip fantana sau nisip am gasit, putand astfel da un raspuns pentru componenta curenta; cat timp mai exista celule M nevizitate reluam procesul. Complexitate timp: O(N*M).