Wartowniku na mur

Tutaj możesz podyskutować na tematy nie kwalifikujące się do żadnego z pozostałych forów

Wartowniku na mur

Postautor: narbej » 04 lut 2015, 22:55

Nie! To nie będzie o wartowniku. To nie będzie o Murze Chińskim, ale warto abyś sobie przeczytał o idei wartownika. Najlepiej w dobrej książce albo ostatecznie w internecie. Kiedyś ja też umieściłem na forum króciutką notkę. wyszukiwanie liniowe z "wartownikiem"
Tutaj -> pytałem o haczyk i tym haczykiem był tam brak wartownika. Wartownicy są wszechobecni. Jest to zero na końcu stringu, jest to -1 na końcu pliku, jest to '\n' na końcu pojedyńczej linii tekstu itd. Tym czym wartownik jest dla stringu [tablicy char], tym samym jest/może być mur dla planszy [nie mylić z macierzą sąsiedztwa]. Sam mur wystarczy, nie potrzeba na nim żadnego wartownika. Z czego budować mur, z byle czego, nie musi być mocny, jedyny warunek, musi się róźnić od wszystkich innych elementów planszy. Może więc to być równie dobrze wartość zero. Jak wielki ma być mur? Najczęściej wystarczy szerokość jednej cegły, ale czasami, np szachy warto postawić dwa razy szerszy [wysokość nie gra roli] mur, aby go konik nie przeskoczył. Znasz zasady gry w szachy?
Czasmi warto postawić najpierw rów z wodą, a dopiero potem mur. Właściwie ten rów, może być na poziomie oceanu/morza, więc będzie natychmiast zalany, a zatem to nie rów, a taka mała ekspansja morza, a dopiero potem budujemy mur, aby zatrzymać i zabespieczyć się przed powodzią i wylewaniem morskiej wody na klawiaturę. Bardzo nie lubi ona słonej wody.
Poruszając się po planszy nie musimy już sprawdzać, czy nie "wyjechaliśmy" poza planszę. Właśnie do tego potrzebowaliśmy muru. Wystarczy teraz tylko sprawdzać na co wjechaliśmy i jeżeli nie na mur, to kontynujemy. Poziome ruchy są bez zmian. Pionowe, zmieniając indeksy, trzeba jeszcze pamiętać, że szerokość planszy trzeba powiększyć o dwie szerokości używanych murków [lub i rowów]. Przykład z lini brzegowej:
Kod: Zaznacz cały
.XXXX.
.X.XX.
XXX...
....X.
......

Najpierw oblewamy wodą, nie żałując jej:
Kod: Zaznacz cały
........
..XXXX..
..X.XX..
.XXX....
.....X..
........
........

Teraz murek:
Kod: Zaznacz cały
nnnnnnnnnn
n........n
n..XXXX..n
n..X.XX..n
n.XXX....n
n.....X..n
n........n
n........n
nnnnnnnnnn
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Wartowniku na mur

Postautor: arekbulski » 07 lut 2015, 12:35

Narbej zapomniał napisać że ta metoda nie jest na sucho, można są zastosować do zadań: ;)
http://pl.spoj.com/problems/AL_05_07/ Linia brzegowa
http://pl.spoj.com/problems/AL_03_04/ Hodowla reniferów
http://pl.spoj.com/problems/PTWPZ098/ Imperium Uhid
arekbulski
 
Posty: 3
Rejestracja: 04 lut 2015, 15:11

Wartowniku na mur

Postautor: narbej » 08 lut 2015, 02:48

Już jestem taki zapominialski.
Tu opisuję murki "prostokątne". Flood fill został wymyślony do kolorowania obszarów dowolnego kształtu [więc i prostokątnych], otoczonych konturem, które mogą zawierać wewnątrz inne dowolne kształty odgrodzone konturem, które, także .. i tak dalej rekurencyjnie ;-)
Flood fill musi mieć jakieś ograniczenie, aby nie rozlał się po całej dostępnej pamięci, bo wtedy tylko ctrl+alt+del ewentualnie młotek.
Sam murek, też jest przydatną rzeczą, nie tylko do flood fila. Przecież w szachach, GO [taka też chińska gra] czy złośliwych liniach, nie ma potrzeby i sensu używania flooda, ale murka jak najbardziej.
Korzystając z murka, nie trzeba po wyciągnięciu ze stosu/kolejki [lub przed włożeniem] sprawdzać czy nie wyszliśmy poza zakres, a potem co dokładnie wyciągnęliśmy [co będziemy wkładać]. Od razu sprawdzamy tylko co wyciągamy [lub wkładamy] do stosu/kolejki. Czy wyciągnęliśmy słoną wodę z morza/oceanue, czy piasek z wyspy, czy cegłę z muru i odpowiednio do tego postępujemy dalej. W szachach analogicznie, albo bardzo podobnie i pamiętajmy, że dodatkowo murek "pochłania" skoki konika a także ruchy ukośne.

Uwzględniając tylko ruchy poziome i pionowe, można zrezygnować, z narożnych cegieł w murkach, ale to przecież nie istotne, to żadna oszczędność.
W praktyce, wysokość murków [wartość] nie ma znaczenia, ale, jeżeli przetwarzana mapa, miałby dodatkowo posłużyć jako materiał do wizualizacji, połączonej z animacją 3D, warto, aby murek był wyższy od najwyższego poziomu oceanu, po przejściu fali flooda, o co najmniej jedną jednostkę i analogicznie wyspy. Wtedy wizualizacja wygląda lepiej i naturalniej, zgodnie z naszymi wyobrażeniami.
Przykład z wcześniejszego wywodu, z narożnymi wartownikami [niepotrzebnymi] i wartownikiem poza murami:
Kod: Zaznacz cały
WnnnnnnnnW
n........n
n..XXXX..n
n..X.XX..n
n.XXX....n
n.....X..n
n........n
n........n
WnnnnnnnnWW

Jak poruszamy się po planszy?
Np używając wskaźnika wsk, z indeksami bardzo podobnie:
Kod: Zaznacz cały
wsk -szer -1 | wsk -szer | wsk -szer +1
----------------------------------------------------
wsk -1       |    wsk    |      wsk +1
---------------------------------------------------
wsk +szer -1 | wsk -szer | wsk +szer +1

gdzie szer to szerokość planszy plus łączna szerokość bocznych murków.
Czy potrafisz sobie, wyobrazić jak to jest zapisane w pamięci? Hmmm, , jeszcze raz nasza plansza, ale już bez Wartowników:
Kod: Zaznacz cały
nnnnnnnnnn
n........n
n..XXXX..n
n..X.XX..n
n.XXX....n
n.....X..n
n........n
n........n
nnnnnnnnnn
, a tak to wygląda w pamięci:
Kod: Zaznacz cały
nnnnnnnnnnn........nn..XXXX..nn..X.XX..nn.XXX....nn.....X..nn........nn........nnnnnnnnnnn

zwróć uwagę na podwójne murki w środku:
nnnnnnnnnnn........nn..XXXX..nn..X.XX..nn.XXX....nn.....X..nn........nn........nnnnnnnnnnn
Czy nie wydaje Ci się, że to o jeden murek za dużo:
nnnnnnnnnn
n........n
n..XXXX..n
n..X.XX..n
n.XXX....n
n.....X..n
n........n
n........n
nnnnnnnnnn

Po dokładnym przemyśleniu dojdziemy do wniosku, dokładnie analizując położenie planszy w pamięci, że faktycznie, lewe murki możemy usunąć:
Kod: Zaznacz cały
nnnnnnnnn
........n
..XXXX..n
..X.XX..n
.XXX....n
.....X..n
........n
........n
nnnnnnnnn

Jeżeli to są szachy, GO, złośliwe linie itd, to w zasadzie już tak musi zostać [oczywiście bez rowu z wodą, pamiętasz, że go dodaliśmy dookoła?]
Przy planszach oceanicznych, tam, gdzie zapuszczamy flooda, nie zawsze zależy nam, aby ograniczać "ruch" poziomy. Brak, murków pionowych, nie ma żadnego wpływu, na ruchy pionowe. Przy ruchach poziomych, to tak jakby fala krążyła poziomo, bez przeszkód, lekko spiralnym ruchem, dookoła kuli ziemskiej. Oba murki poziome, na samej górze i dole są jednak porzebne - ochraniają pamięć przed "zalaniem" - wyjśćiem wskażnika lub indeksów, poza dozwolony obszar pamięci.
Czyli teraz, dla linii brzegowych możemy zrezygnować też z murka pionowego-prawego i otrzymamy:
Kod: Zaznacz cały
nnnnnnnn
........
..XXXX..
..X.XX..
.XXX....
.....X..
........
........
nnnnnnnn
Jeżeli przeprowadzimy analogiczną analizę dla wcześniej dodanych rowów z wodą, dojdziemy do wniosku [czy aby na pewno?, może kłamię] że wystarczą tylko oba poziome i jeden pionowy rów z wodą, po prawej. Teraz, po usunięciu lewego, pionowego rowu z wodą, mapa wygląda tak:
Kod: Zaznacz cały
nnnnnnn
.......
.XXXX..
.X.XX..
XXX....
....X..
.......
.......
nnnnnnn

Czy wiesz jak jest wczytywany string? Jest on wczytywany, do pierwszego białego znaku [np: ' ', \t', '\n', itd], i do końca stringu dopisywane jest zero. Czy jak trochę zmodyfikuję rów, to zorientujesz się, co się tu stało?:
Kod: Zaznacz cały
nnnnnnn
......\0
.XXXX.\0
.X.XX.\0
XXX...\0
....X.\0
......\0
......\0
nnnnnnn

A czy wiesz, jak funkcja gets() wczytuje dane do bloku pamięci a jeszcze lepiej funkcja fgets()? Różnica, jest taka, że zamist zamieniać znaki '\n' na '\0' zostawia '\n' bez zmian:
Kod: Zaznacz cały
nnnnnnn
......\na
.XXXX.\n
.X.XX.\n
XXX...\n
....X.\n
......\n
......\n
nnnnnnn W
Do poruszania się po takiej planszy, trzeba na nowo policzyć szerokośc planszy - wróć do wcześniejszej tabelki ze wskaźnikiem wsk.

I można wstawić na sam koniec wartownika, może nie na mur, ale na samym końcu, dolnego, najniższego muru.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Wartowniku na mur

Postautor: narbej » 08 lut 2015, 10:59

Jeszcze raz ostatnia mapa +Wartownik, a nawet dla bezpieczeństwa dwóch, dwie litery WW na końcu mapy poniżej:
Kod: Zaznacz cały
nnnnnnn
......\n
.XXXX.\n
.X.XX.\n
XXX...\n
....X.\n
......\n
......\n
nnnnnnnWW

Jeżeli mamy do przetworzenia więcej niż jedną mapę to: "Czy za każdym razem musimy budować górny murek?"
Nie!
Możemy jednorazowo, wybudować odpowiednio długi, przewidując najszerszą mapę a dane terenowe mapy wczytywać za każdym razem w odpowiednie miejsce pamięci - bezpośrednio za zakończeniem murka. A co z rowem. Tu już gorzej - po "puszczeniu" flooda, poziom wody nieznacznie się podnosi, więc woda w rowie też i przy następnej mapie byłoby to trochę kłopotliwe. Murek na dole mapy i ewentualny rów, musimy budować każdorazowo. Tak wygląda ostatecznie taka sytuacja, dla pierwszej mapy z zadania linia brzegowa.
Kod: Zaznacz cały
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
......\n
.XXXX.\n
.X.XX.\n
XXX...\n
....X.\n
......\n
......\n
nnnnnnnWW

Czy to jakaś kolosalna optymalizacja? Bardzo wątpię, ale jak chcesz oszukać czas, to nawet milionowe ułamki sekudy są ważne.
Nie musisz używać murków. Ale jeżeli stawiasz murek +ewentualnie rów z wodą, to stawiaj go z głową i odpowiednio szeroki, "wysoki" i z dobrego "budulca".
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51


Wróć do Forum ogólne

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron