Editorial for Boje
Submitting an official solution before solving the problem yourself is a bannable offence.
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
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 , ovaj pristup bi bio vrlo spor za najveće test primere.
Posmatrajmo primer gde je i . 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
Sada ćemo objasniti kako da od ulaza napravimo graf koji ima čvorova i 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 .
Posmatrajmo sada kolonu koja ima bar jedno crno polje. Ako kolona ima crnih polja tada se ona može izdeliti u ili manje nizova uzasotpnih neobojenih polja. Svaki od tih nizova ćemo posmatrati kao poseban čvor. Takvih čvorova ima najviše .
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 lista čvorova prve, a neka je lista čvorova druge kolone. Svaki čvor je predstavljen kao par , što znači da je podniz uzastopnih neobojenih polja koji se u odgovarajućoj koloni pružaju između redova i . Pretpostavimo da su čvorovi u i 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 i .
Neka je trenutni čvor koji obrađujemo u , a trenutni čvor koji obrađujemo u . Na početku, je prvi čvor iz , a je prvi čvor iz . Primenjujemo sledeće sve dok nismo prošli sve čvorove iz bar ili :
- Ako , postavimo da bude sledeći čvor u .
- Ako , postavimo da bude sledeći čvor u .
- Inače, dodamo granu između i . Ako je , onda postavimo da bude sledeći čvor u , a inače postavimo da bude sledeći čvor u .
Nije teško proveriti da se na ovaj način zaista definišu sve grane između čvorova u i . Pored toga, svaki put kad se doda grana čvor ili čvor se pomere za jedan mesto. To znači da se u ovom procesu doda najviše grana. Pošto je svaka kolona susedna sa najviše dve druge kolone i pošto smo rekli da je ukupan broj čvorova , ovim procesom se doda najviše 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 se može uraditi u vremenu , tako da je ukupna složenost celog algoritma .
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 na čvorova, sa grana, povezanih oblasti i komponenti, tada važi . Ovu formulu možemo iskoristiti da rešimo zadatak na sledeći način.
Za četiri polja koja imaju koordinate , , , 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 i , i granu koja spaja polja , ). 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 grana, tako da vrednost možemo lako naći, na primer, DFS algoritmom.
Koristeći navedenu formulu možemo da izračunamo . Ali šta predstavlja ? 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 , , ) i rotacijama ove konfiguracije činiti povezane oblasti. Pored ovih oblasti, 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 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 ; (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.
Comments