Analiza

Lako je videti da se ovaj zadatak može svesti na traženje broja povezanih komponenti među poljima koja nisu obojena. Svaku takvu komponentu možemo obojiti novom obojom. U ostatku rešenja ćemo opisati kako se broj povezanih komponenti može efikasno naći pod ograničenjima datim u ovom zadatku.

Rešenje u ~O(N \cdot M)~

Da bismo pronašli broj komponenti, jednostavno možemo da primenimo Depth First Search (DFS) algoritam od svakog neobojenog polja koje nismo do sada ovim algoritmom posetili. Pošto broj čvorova i grana u grafu koji predstavljaju neobojena polja ima složenost ~O(N \cdot M)~, ovaj pristup bi bio vrlo spor za najveće test primere.

Posmatrajmo primer gde je ~N = M = 10^9~ i ~K = 10^5~. U tom primeru postoje "veliki" delovi table koji su neobojeni a povezani. Intuitivno, umesto da svako polje tih "velikih" delova posmatramo kao čvor, bilo bi zgodno ako bismo ceo "veliki" deo posmatrali kao jedan čvor. U tom slučaju bi gore opisani DFS-pristup imao daleko manju složenost. Naravno, glavno pitanje ovde je kako izabrati velike delove tako da je zgodno sa njima raditi, a usput svesti broj čvorova koje posmatramo na mali broj. U ostatku rešenja ćemo se fokusirati na ovo pitanje.

"Veliki" delovi table i rešenje u ~O(K \cdot \log{K})~

Sada ćemo objasniti kako da od ulaza napravimo graf koji ima ~O(K)~ čvorova i ~O(K)~ grana.

Čvorovi

Najpre, uzastopne kolone koji nemaju ijedno crno polje ćemo posmatrati kao jedan čvor. Pošto je, sem prvog i poslednjeg, svaki takav čvor ograničen kolonama koje imaju bar jedno crno polje, broj takvih čvorova je najviše ~K + 1~.

Posmatrajmo sada kolonu koja ima bar jedno crno polje. Ako kolona ima ~t~ crnih polja tada se ona može izdeliti u ~t + 1~ ili manje nizova uzasotpnih neobojenih polja. Svaki od tih nizova ćemo posmatrati kao poseban čvor. Takvih čvorova ima najviše ~2 K~.

Grane

Da bismo izlistali grane, posmatraćemo po dve susedne kolone i čvorove koje one definišu, pod uslovom da bar jedna od kolona ima bar jedno crno polje. (Dve susedne kolone koje nemaju crna polja su deo istog čvora.) Neka je ~C_1~ lista čvorova prve, a neka je ~C_2~ lista čvorova druge kolone. Svaki čvor ~v~ je predstavljen kao par ~(a, b)~, što znači da je ~v~ podniz uzastopnih neobojenih polja koji se u odgovarajućoj koloni pružaju između redova ~a~ i ~b~. Pretpostavimo da su čvorovi u ~C_1~ i ~C_2~ sortirani u rastućem poretku po prvoj koordinati. Tada, se sledeći algoritam može primeniti da se nađu sve grane između čvorova u ~C_1~ i ~C_2~.

Neka je ~v_1 = (a_1, b_1) \in C_1~ trenutni čvor koji obrađujemo u ~C_1~, a ~v_2 = (a_2, b_2) \in C_2~ trenutni čvor koji obrađujemo u ~C_2~. Na početku, ~v_1~ je prvi čvor iz ~C_1~, a ~v_2~ je prvi čvor iz ~C_2~. Primenjujemo sledeće sve dok nismo prošli sve čvorove iz bar ~C_1~ ili ~C_2~:

• Ako ~b_1 < a_2~, postavimo ~v_1~ da bude sledeći čvor u ~C_1~.
• Ako ~b_2 < a_1~, postavimo ~v_2~ da bude sledeći čvor u ~C_2~.
• Inače, dodamo granu između ~v_1~ i ~v_2~. Ako je ~b_1 < b_2~, onda postavimo ~v_1~ da bude sledeći čvor u ~C_1~, a inače postavimo ~v_2~ da bude sledeći čvor u ~C_2~.

Nije teško proveriti da se na ovaj način zaista definišu sve grane između čvorova u ~C_1~ i ~C_2~. Pored toga, svaki put kad se doda grana čvor ~v_1~ ili čvor ~v_2~ se pomere za jedan mesto. To znači da se u ovom procesu doda najviše ~|C_1| + |C_2|~ grana. Pošto je svaka kolona susedna sa najviše dve druge kolone i pošto smo rekli da je ukupan broj čvorova ~K + 1 + 2 K~, ovim procesom se doda najviše ~2 (3K + 1)~ grana.

Da bismo pronašli broj povezanih komponenti nad ovakvim grafom možemo da primenimo DFS; alternativno, umesto DFS-a možemo iskoristiti union-find strukturu. Cortiranje čvorova u koloni ~C~ se može uraditi u vremenu ~O(|C| \log{|C|})~, tako da je ukupna složenost celog algoritma ~O(K \log{K})~.

Alternativno rešenje

Ovaj zadatak sa takođe može rešiti primenom Ojlerove formule za planarne grafove. Naime, ako nam je dat planaran graf ~G~ na ~n~ čvorova, sa ~m~ grana, ~f~ povezanih oblasti i ~c~ komponenti, tada važi ~n - m + f = 1 + c~. Ovu formulu možemo iskoristiti da rešimo zadatak na sledeći način.

Za četiri polja koja imaju koordinate ~(x, y)~, ~(x, y + 1)~, ~(x + 1, y)~, ~(x + 1, y + 1)~ kažemo da čine 2x2 kvadrat.

Zamislićemo da je tabla oivičena trakom crne boje. Celu tu traku ćemo posmatrati kao jedan čvor. Potom, u centar svakog crnog polja ćemo staviti čvor. Povezaćemo dva čvora granom ako odgovarajuća crna polja dele makar jedno teme, i pored toga izbacićemo grane koje spajaju naspramna polja u 2x2 crnom kvadratu (granu koja spaja polja ~(x, y)~ i ~(x + 1, y + 1)~, i granu koja spaja polja ~(x + 1, y)~, ~(x, y + 1)~). Ove grane izbacujemo da bismo očuvali planarnost. Primetimo da je ova definicija susednih crnih polja drugačija nego ona u postavci zadatka. Takođe ćemo povezati traku koja oivičava tablu sa svakim čvorom koji dodiruje ivicu table, tj., sa svakim čvorom koji se nalazi u prvom ili u poslednjem redu ili u prvoj ili u poslednjoj koloni. Ovaj graf je planaran. Pored toga, graf ima ~O(K)~ grana, tako da vrednost ~c~ možemo lako naći, na primer, DFS algoritmom.

Koristeći navedenu formulu možemo da izračunamo ~f~. Ali šta predstavlja ~f~? Najpre, svaka četiri čvora koja čine 2x2 kvadrat će u ovoj definiciji planarnog grafa formirati jednu povezanu oblast. Takođe će i svaka tri čvora u "G obliku" (tj. imaju koordinate ~(x, y)~, ~(x, y + 1)~, ~(x + 1, y)~) i rotacijama ove konfiguracije činiti povezane oblasti. Pored ovih oblasti, ~f~ broji povezane oblasti koje odgovaraju neobojenim poljima, što je upravo broj onih oblasti koje su rešenje ovog problema. Dakle, da bismo rešili ovaj problem, potrebno je da od ~f~ oduzmemo 2x2 crne kvadrate.

Za implementiranje DFS-a možemo smestiti sva crna polja u hash mapu, ili na primer u strukturu map u C++. Pristupom ovoj mapi je onda lako naći koje susede ima dati čvor.

Da rezimiramo, da bismo rešili problem, potrebno je da: (1) napravimo graf kao što je to opisano; (2) izračunamo ~c~; (3) prebrojimo 2x2 crne kvadrate, i prebrojimo crne kvadrate koji čine "G oblik" i njegove rotacije; i (4) koristeći navedenu formulu izračunamo rešenje ovog problema.