Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Zadanie O - Sokoban
Idź do strony Poprzedni  1, 2, 3  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 23:01, 03 Maj 2006    Temat postu:

Fakt, że zmieściłem się w pamięci, graniczyło z cudem :P . Inna sprawa, że ten sposób z OI jest stosunkowo łatwy w implementacji i nie trzeba kombinować z zawracaniem, bo to jest już określone w grafie stanów. Nie trzeba też za wiele debuggować, no chyba że się popełnia takie błędy jak ja i wychodzi się z programu przed wczytaniem wszystkich danych z testu :P .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Śro 23:04, 03 Maj 2006    Temat postu:

dla mnie to on nieintuicyjny jest...chociaz moze wynika to z tego ze czytalem go cale 2 min po czym pomyslalem "a ch** z tym...moje lepsze:P" ale to nei zmienia faktu ze smierdzi i jest wolniejszy niz roziwazania BFSowe na jednym grafie :p
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 23:15, 03 Maj 2006    Temat postu:

Kap00ch, ale Twoje rozwiązanie jest bardziej kombinowane i podatne na błędy :P . A co do prędkości to nie jestem przekonany, że Twoje rozwiązanie jest znacząco szybsze. Oba algorytmy są w końcu liniowe względem ilości pól w hurtowni.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Śro 23:19, 03 Maj 2006    Temat postu:

nie wiem jak to z OI ale moje jest n*m*3 :] (a na bledy to i owszem...:P ale pominmy ta kwestie gdyz aksjomatem jest ze kap00chowe programy same w sobie sa bugiem:P) ...chociaz i tak wg mnie mozna to jeszcze przyspieszyc...tutaj akurat by pasil idealnie jakis A* albo cos z IDSow...no al uparli sie na ta swoja dwuspojna :P chociaz w sumie przyznam sie ze na poczatku jej nie docenialem :]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 23:26, 03 Maj 2006    Temat postu:

Szczerze mówiąc, to jak zobaczyłem to zadanie, to użycie dwuspójnej wydało mi się w miarę oczywiste. No a Ty się upierałeś, że Twoje Dijkstry są bardziej intuicyjne - Twoja sprawa :P . Tak to jest, jak się zna bardziej zaawansowane metody i nie widzi się przez to najprostszych rozwiązań... (ale: najprostsze<>najbardziej intuicyjne)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 0:23, 04 Maj 2006    Temat postu:

To ja moze troche bardziej szczegolowo opisz moj algorytm. Moj main wyglada tak (tylko nie zrzynac :P):
Kod:

begin
   readln(z);
   for i := 1 to z do
      begin
         readdata;
         creategraph;
         BIC;
         DFS;
         BFS;
      end;
end.

I teraz po kolei, co robia poszczegolne procedury
1. readdata
Jak sama nazwa wskazuje wczytuje dane. Najpierw oczywiscie wymiary planszy a potem char po charze po kolei wszystko. Jak to wczytuje? Otoz jesli pole jest sciana wstawiam do tablicy 0, a jesli czymkolwiek innym to wstawiam kolejna liczbe naturalna i, jednoczesnie do osobnej tablicy 10000 x 2 na i-te miejsce wstawiajac wspolrzedne tego punktu. Oczywiscie polozenie kolesia, paczki i target zapamietuje w 3 zmiennych gdzies na boku. I teraz mam taka fajna strukture ze majac wspolrzedne punktu moge blyskawiacznie stwierdzic czy jest to punkt "wolny" oraz poznac jego numer, i vice versa - majac numer moge miec od razu wspolrzedne.
2. Creategraph
Tworzy graf zlozony z tych wlasnie wolnych ponumerowanych pol. Trzymam go w tablicy 10000x4x2 oraz pomocniczej 10000. Dla i-tego wierzcholka trzymam w pomocniczej tablicy liczbe sasiadow a w glownej maksymalnie 4 pary liczb - opisy tych sasiadow. Opis sklada sie z numeru sasiada i numeru krawedzi ktora do niego prowadzi. Po co numery krawdedzi? Otoz mam jeszcze jedna tablice 40000 gdzie bede trzymal numer dwuspojnej skladowej do ktorej nalezy dana krawedz.
3. BIC
Zapuszczam na tym grafie algorytm z wykladu i znajduje dwuspojne skladowe, ktore zapisuje w tej tablicy o ktorej przed chwila pisalem.
4. DFS
Z punktu w ktorym jest dozorca zapuszczam DFSa zeby sprawdzic czy dozorca moze dojsc do paczki. Przy pierwszym pojawieniu sie dozorcy obok paczki przerywam DFSa i zapamietuje nowa pozycje dozorcy.
5.BFS
I to jest najwiekszy myk, gdyz puszczam BFSa po grafie ktorego nie ma :) Tzn nie tworze go calego tylko tak tymczasowo kolejne "warstwy" na potrzeby BFSa. Wierzcholek w tym grafie sklada sie z pozycji paczki (przypominam ze jest to jedna liczba - gdyz mam te fajne zaleznosci zrobione w pkt 1) oraz zmiennej dir przyjmujacej wartosci od 1 do 4 mowiace z ktorej strony paczki jest dozorca. Czyli moj domniemany graf moglby miec maksymalnie 10000*4 wierzcholkow. Takie tez mam dla niego tablice visited (boolowska) i dist (odleglosci). I teraz pierwszemu wierzcholkowi ustwiam visited na true, dist na 0 i hop do kolejki. I teraz robie klasycznego BFSa - dopoki kolejka niepusta wycigniej pierwszy z kolejki i przetworz. Jak wyglada przetworzenie? Najpierw sprawdzam czy z tego wierzcholka moge osiagnac inny poprzez obejscie paczki (czyli zmienia sie tylko dir). Robie to przy uzyciu dwuspojnych skladowych. Jezeli krawedz od paczki do polozenia aktualnego i do jakiegos innego poozenia (dozorcy) sa w tej samej dwuspojnej to znaczy ze moge obejsc i taki wierzcholek dodaje do kolejki UWAGA - przepisujac wartosc dist bez dodawania 1. Potem sprawdzam czy moze paczke przesunac i jesli tak to dodaje do kolejki nowy wierzcholek z innym polozeniem paczki i tym samym direm. No i teraz sprawdzam czy czasem paczka nie trafila do celu - jesli tak to przerywma cala zabawe i wypisuje wynik.

Mam nadzieje ze to co napisalem jest zrozumiale... Wiem ze moje rozwiazanie nie jest ani najszybsze (jesli mowimy o stalej) ani tym bardziej najoptymalniejsze pamieciowo, ale wedlug mnie jest ono calkiem czytelne. No i nie bawie sie w jakas obsluge zawracania czy inne rzeczy o ktorych pisali moi szanowni przedmowcy :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Czw 8:28, 04 Maj 2006    Temat postu:

No to mamy, hansu, bardzo podobne rozwiązania. Z tym, że ja w BIC od razu sprawdzam to, co Ty w osobnym DFSie. No i jawnie konstruuję graf stanów, a nie na bieżąco, przy czym wynik wypisuję po przeglądnięciu całego grafu.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Czw 8:35, 04 Maj 2006    Temat postu:

hansu:
Zamiast pisać osobnego DFS-a można sprawdzić BFS-em (który i tak napisać trzeba) czy dozorca może dojść do paczki. Trochę wolniej, ale za to kod krótszy. Wystarczy BFS-owi dorobić parametr bool'owski.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Sob 17:44, 06 Maj 2006    Temat postu:

hansu napisał:
Najpierw sprawdzam czy z tego wierzcholka moge osiagnac inny poprzez obejscie paczki (czyli zmienia sie tylko dir). Robie to przy uzyciu dwuspojnych skladowych. Jezeli krawedz od paczki do polozenia aktualnego i do jakiegos innego poozenia (dozorcy) sa w tej samej dwuspojnej to znaczy ze moge obejsc i taki wierzcholek dodaje do kolejki UWAGA - przepisujac wartosc dist bez dodawania 1.


Mam takie pytanie do tego fragmentu, skoro sprawdzamy czy mozna obejsc paczke i jezeli tak to dodajemy do kolejki z nowym kierunkiem to czemu odleglosc sie nie zmienia? mi sie wydaje ze obchodzac paczke odleglosc moze sie znacznie zwiekszyc jezeli dlugo bedziemy "szli" do tej paczki zeby miec inny kierunek. Ale skoro hansu juz zrobil to pewnie mam blad w mysleniu... tylko jaki?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Sob 17:48, 06 Maj 2006    Temat postu:

No bo jako odpowiedz masz podac ilosc przesuniec paczki. I ta moja "odleglosc" to wlasnie to. Jesli w tym "wirtualnym grafie" krawedz odpowiada przesunieciu to ma wage 1, a jesli tylko obejsciu paczki, to wtedy 0.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Sob 17:51, 06 Maj 2006    Temat postu:

ehh no tak... od nastepnego razu czytam dokladnie tresc zadan:] dzieki hansu :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
krzycho
pijak



Dołączył: 09 Lis 2005
Posty: 151
Przeczytał: 0 tematów

Skąd: Radom

PostWysłany: Sob 22:31, 06 Maj 2006    Temat postu:

Cytat:
Potem sprawdzam czy moze paczke przesunac i jesli tak to dodaje do kolejki nowy wierzcholek z innym polozeniem paczki i tym samym direm.


Mam pytanie do cytowanego fragmentu, jak sprawdzasz czy mozesz przesunac paczke? Czy wystarczy sprawdzic czy to pole(gdzie chcemy przesunac pake) nie jest sciana ?? czy trzeba sprawdzcic czy krawedz od paczki do nowej pozycji paczki oraz krawedz od paczki do poz. kolesia maja ten sam bcc?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Sob 23:04, 06 Maj 2006    Temat postu:

Nie musza miec tej samej bcc. Bo magazynier nie obchodzi paczki. Wystarczy sprawdzic czy pole po drugiej stronie paczki (w stosunku do magazyniera) jest wolne (czyli nie jest sciana ;))
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Sob 23:49, 06 Maj 2006    Temat postu:

[link widoczny dla zalogowanych]

Enjoy! ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Sob 23:52, 06 Maj 2006    Temat postu:

Ma ktos moze jakies testy wlasnej roboty do tego zadanka? na virgo mam wszysto Ok a athina mowi ANS...


Edited: a jednak przeszlo, nie wyzerowalam jednej zmiennej:]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Nie 14:46, 07 Maj 2006    Temat postu:

Mam prośbe, czy mógłby mi ktoś przesłac na e-maila wzorcówke z finału przerobiną, żeby działała pod fp, bez wczytywania z pliku, bo coś mi nie wychodzib :cry: , jakieś blędy wyskakują, nawet jeśli wrzucam kompatybilność z TP.

Bylbym wdzięczny
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Nie 14:56, 07 Maj 2006    Temat postu:

Nie wiem czy ktos ja przerabial, bo strasznie kijowa jest ta wzorcowka... Jakies rekurencje przez goto i inne archaizmy. Jak chcesz to moge wystawic mojego execa... Znajdziesz go [link widoczny dla zalogowanych]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Sob 19:49, 13 Maj 2006    Temat postu:

rowniez mam schematyczne rozwiazanie:
1) czytaj dane
2) BIC
3) BFS
jednak nie tworze zadnego grafu 'grafu', tylko moja plansze[1..100,1..100] of Pole traktuje jak graf, czyli wszystkie 4 drogi prowadza do pola, ktore rozni sie jedna wspolrzedna o |x|=1, takze wystarczy ze sprawdze czy dane pole to nie sciana, oraz czy nie zostalo odwiedzone [wszystko wartosci logiczne]
natomiast moj BFS w zasadzie nie zwraca uwagi czy pole odwiedzone czy nie, tylko sprawdza czy dana droga juz szedlem, dlatego mam 4 drogi w kazdym polu, reprezentowane przez wartosci logiczne :) wiec defacto tworze graf zorientowany, kazda krawedz niezorientowana stanowia dwie drogi... na stosie w BFS odkladam aktualna pozycje dozorcy, paczki, ile paczka przebyla juz drogi, oraz dla ulatwienia nr drogi ktora laczy dozorce z paczka...
na pewno nie jest to najoptymalniejsze rozwiazanie, co prawda nie trace czasu na budowe grafu, a po BIC nie musze aktualizowac zadnych wartosci logicznych, czy tez tworzyc jakiegos nowego grafu, ale dochodzi conajmniej jeden warunek wiecej do sprawdzenia za kazdym razem... [nie mam porownania - na virgo mialem w sumie 0,03 s.], w kazdym badz razie to rozwiazanie wydaje mi sie moze nie najprostsze, ale dosc intuicyjne ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
swiecmich
pijak



Dołączył: 09 Lis 2005
Posty: 62
Przeczytał: 0 tematów

Skąd: pomorze :D

PostWysłany: Nie 14:44, 14 Maj 2006    Temat postu:

Mam dosyc dziwny problem z tym zadaniem. Przy kompilacji poleceniem "fpc O.pas" moj program daje dokladnie takie wyniki jak w plikach *.out z testerki matea. Jesli jednak skompiluje go z parametrami "fpc -Sgic -Xs -viwnh -OG2p3 O.pas" to daje zupelnie inne wyniki, czasami sie zapetla itp. Jesli usune parametr -OG2p3 to chyba dziala juz poprawnie. Niestety athina i testerka kompiluja z tym parametrem. Wie ktos moze dlaczego tak sie dzieje ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Nie 15:09, 14 Maj 2006    Temat postu:

Niestety padłeś kolejną ofiarą optymalizatora FreePascala. Trzeba gdzieś wstawić linijkę typu:
Kod:
p := p;

gdzie p jest którąś z Twoich zmiennych. W fazie debuggowania na pewno tą zmienną znajdziesz ;] .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Nie 15:16, 14 Maj 2006    Temat postu:

Najprawdopodobniej któryś wskaźnik. Najlepiej jesli masz jakąś procedurę zerojącą to jej kod wrzucić w takie miejsce zeby ktoś na 100% skorzystał z tych zmiennych które wyzerowałeś.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
:-)
pijak



Dołączył: 09 Mar 2006
Posty: 63
Przeczytał: 0 tematów

Skąd: Zalesie Górne

PostWysłany: Nie 18:35, 14 Maj 2006    Temat postu:

Pomocy, pomocy! Słoń, straszliwy Słoń!
Pomocy, pomocy! Słoniowy Strach! Słoniocy! Słoniocy! Strachowy Pom! Pomocny Strach! Słoniocy!

M... m... ma ktoś może jakieś złośliwe testy do tego? Koniecznie złośliwe, bo tylko takie są skuteczne w walce ze Słoniem! Te na virgo (z oi) nie sa wystarczająco wredne - same OK, a athinowy Słoń nieugięcie broni się ANSem!
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
r4ku
żul



Dołączył: 09 Lut 2006
Posty: 722
Przeczytał: 0 tematów

Skąd: klikash? :D

PostWysłany: Nie 20:09, 14 Maj 2006    Temat postu:

poszlo, po wielogodzinnej walce z debugerem w dloni... zadanie paskudne, ale rozwiazanie zapewnia duza satysfakcje... pomimo ze przez magazyniera nie umiem nic na algebre i analize a jutro kolos poprawkowy z jednego i kartkoweczka z drugiego...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Nie 20:21, 14 Maj 2006    Temat postu:

@:-)
na virgo kazdy test sklada sie z jednego zestawu, natomiast testy na Athinie skladaja sie z wielu zestawow, wiec moze nie ustawiasz jakis poczatkowych wartosci zmiennych? tez mialem taki blad, okazalo sie, ze nie ustawialem wartosci niektorych zmiennych logicznych [no skoro zawsze ustawiaja sie na false ;)]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Nie 20:28, 14 Maj 2006    Temat postu:

Skoro kap00cha nie ma :P to pozwole sobie zamieścić test jego autorstwa który dość ułatwia sprawe :) Przynajmniej mi pomógł...

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony Poprzedni  1, 2, 3  Następny
Strona 2 z 3

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin