Bih li mogao dobiti 1. i 2. primjer zadatka.
Moj email je frane.kurtovic@gmail.com
Moj email je frane.kurtovic@gmail.com
Kredit
Za zadatke sa skorijih takmicenja ima test-primera na www.yuoi.nis.edu.yu.
http://www.yuoi.nis.edu.yu/takmicenja/2007.2.drz/3.kredit/kredit.tests.rar
http://www.yuoi.nis.edu.yu/takmicenja/2007.2.drz/3.kredit/kredit.tests.rar
Probao sam te primjere i moj program daje tocna rjesenja.
Kad posaljem onda mi prodje samo 5 primjera, a na ostalim je krivo rjesenje.
Ne znam zasto.
Kad posaljem onda mi prodje samo 5 primjera, a na ostalim je krivo rjesenje.
Ne znam zasto.
Heh... call for admin :)
Bi li netko mogao nesto pogledati sto je sa ovim zadatkom?
U zadatku pise da prepreku oznacavaju znakovi 'x', a u primjerima su zapravo znakovi 'X'.
To je jedina greska, koliko ja znam.
To je jedina greska, koliko ja znam.
To sam primjetio i popravio kod slanja koda, ali svejedno nije radilo.
Kada skinem primjere sa već navedene stranice, sve mi prodje, ali ne znam zasto mi ne prolazi kada posaljem.
Kada skinem primjere sa već navedene stranice, sve mi prodje, ali ne znam zasto mi ne prolazi kada posaljem.
Mozda ti neka varijabla nije inicijalizirana?
Evo ja sam se namucio dok nisam uradio zadatak, pa da bih eventualno nekoga postedeo muke, ostavicu svoju ideju.
U polju matrice A[P][Q] izracunam duzinu najkraceg puta od polja (P,Q) do bilo koje trafike. Kako? Pa pretragom u sirinu, ali paralelno iz svake trafike. To (u prevodu) znaci da BFS prvo popunjava susedna polja prve trafike, zatim susedna polja druge, pa trece, itd... To se moze postici ubacivanjem na pocetak reda svih onih polja na kojima su trafike i pustanjem samo jednog BFS-a nad tim redom.
Kada imamo izracunatu matricu A, moramo naci MIN i MAX, vrijednosti trazene u zadatku. Ja sam u pocetku mislio da ih trazim samo u poljima "oko" fontane, odnosno u poljima do kojih se moze stici u K koraka od EX i EY (koordinate fontane). Dakle, ako je abs(EX-I) + abs(EY-J) < K, moze se stici do polja (I,J).
Jes', al' malo sutra! Nisam uzeo u obzir zidove, i tu sam izgubio dosta vremena. Mora se pustiti jos jedan BFS iz fontane koji moze da ide do K-tog nivoa u dubinu u drvetu pretrage. Samo tako se mogu proveriti polja do kojih se zaista moze stici u najvise K koraka (minuta, ista stvar)...
Nadam se da sam nekome pomogao.
P.S. Sa zadatkom je sve OK, osim tog ulaza na kome se pojavljuje 'X' a ne 'x'...
U polju matrice A[P][Q] izracunam duzinu najkraceg puta od polja (P,Q) do bilo koje trafike. Kako? Pa pretragom u sirinu, ali paralelno iz svake trafike. To (u prevodu) znaci da BFS prvo popunjava susedna polja prve trafike, zatim susedna polja druge, pa trece, itd... To se moze postici ubacivanjem na pocetak reda svih onih polja na kojima su trafike i pustanjem samo jednog BFS-a nad tim redom.
Kada imamo izracunatu matricu A, moramo naci MIN i MAX, vrijednosti trazene u zadatku. Ja sam u pocetku mislio da ih trazim samo u poljima "oko" fontane, odnosno u poljima do kojih se moze stici u K koraka od EX i EY (koordinate fontane). Dakle, ako je abs(EX-I) + abs(EY-J) < K, moze se stici do polja (I,J).
Jes', al' malo sutra! Nisam uzeo u obzir zidove, i tu sam izgubio dosta vremena. Mora se pustiti jos jedan BFS iz fontane koji moze da ide do K-tog nivoa u dubinu u drvetu pretrage. Samo tako se mogu proveriti polja do kojih se zaista moze stici u najvise K koraka (minuta, ista stvar)...
Nadam se da sam nekome pomogao.
P.S. Sa zadatkom je sve OK, osim tog ulaza na kome se pojavljuje 'X' a ne 'x'...
@igor
malo sam Äitao tvoj kod, i kada radiÅ¡ bfs, napravi si matricu boolova (ili niz) i inicijaliziraj ih na false, a kad prvi put doÄ‘eÅ¡ u neko polje staviÅ¡ na true, tako ćeÅ¡ znati gdje si bio a gdje ne, jer ti onako koristiÅ¡ set, i tvoja provjera da li si bio u nekome je O ( lg N ), i oznaÄavanje nekoga isto O( lg N ), sa matricom ili nizom boolova to ćeÅ¡ raditi u O( 1 )
malo sam Äitao tvoj kod, i kada radiÅ¡ bfs, napravi si matricu boolova (ili niz) i inicijaliziraj ih na false, a kad prvi put doÄ‘eÅ¡ u neko polje staviÅ¡ na true, tako ćeÅ¡ znati gdje si bio a gdje ne, jer ti onako koristiÅ¡ set, i tvoja provjera da li si bio u nekome je O ( lg N ), i oznaÄavanje nekoga isto O( lg N ), sa matricom ili nizom boolova to ćeÅ¡ raditi u O( 1 )