Zadanie z OI - Przekroczenie limitu pamieci

Question

Witam, Dzisiaj zabrałem się za zadanie Grzbiety i doliny. Po jakimś czasie główkowania i implementacji wysłałem swoje rozwiązanie. Ku mojemu zdziwieniu program przekroczył limit pamięci.

kod: https://ideone.com/fJl9Tx

Próbowałem już pozbyć się tablic row[] oraz col[] i do pętli tworzącej graf wstawić to samo co w pętli nadpisującej wartości row[] oraz col[] (tej, w której wczytuję arr[]). Niestety pozbycie się ok. 8MB dalej nie pomaga. Ma ktoś pomysł gdzie program zżera aż tyle pamięci?

Comments

(uwaga na boku: iterację się robi od 0 do <N, a nie od 1 do <=N.)

Answer 1

Ma ktoś pomysł gdzie program zżera aż tyle pamięci?

No, w tym że masz z góry zadeklarowane tablice milionów elementów, w tym milion vectorów. Takich tablic powinno być 0, nic nie powinno być tak deklarowane z góry globalnie.

Nie rozumiem zbytnio po co większość tych tablic jest - `row` i `col` są niepotrzebne, bo zawsze wiesz w którym wierszu jesteś, nie musisz tego przechowywać. Tak samo milion vectorów `v` (z których prawie każdy przechowuje po 8 elementów - co samo z siebie od razu sięga limitu, bo 4b*8*milion==32MB) też są kompletnie niepotrzebne; to nie jest jakiś losowy złożony graf którego strukturę trzeba zapisać, to jest zwykła siatka 2d - nie trzeba zapamiętywać że obok punktu (100, 100) jest punkt (100, 101), bo to jest z góry wiadome.

Comments

Pierwszy element tablicy to tab[0]. Wszystko ogólnie jest indeksowane od 0. Jak jedziesz od 1 to teraz wszędzie musisz ostrożnie żonglować z +1/-1 (jak teraz sam robisz np w #define row) i jest ryzyko że czasem przypadkiem zgubisz pierwszy element tablicy/vectora (jak chyba teraz robisz) albo wyjdziesz poza tablicę.

---

nie muszę, bo wektor arr jest zadeklarowany z jakimś śmieciem na początku, więc mogę już spokojnie od jedynki lecieć

---

No super, to jeszcze jedną rzecz specjalnie kombinujesz tylko po to żeby nie indeksować od 0 jak reszta świata :P To to jest tylko jeszcze jedna komplikacja którą by można wyrzucić.

---

wiesz co, zrobiłem jeszcze raz, tym razem bez tych niepotrzebnych wektorów, map, itd, ale zamiast 70 daje mi 90 i ten sam błąd (przekroczenie pamięci. Tym razem tylko jeden test uległ temu błędowi, a nie 3 jak wcześniej).

Tutaj kod: https://ideone.com/GYq0N3

---

Nie wiem jak to się ma do "przekroczenia pamięci", ale ogólnie DFS jest tutaj słabym wyborem algorytmu. Sprawdź co się stanie jak dasz mu na wejście płaską powierzchnię 1000x1000.