Author |
Message |
17/12/2018 18:18:07
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
Ja iskucav zadaca ljubov. Imam 2 bfs, ednoto od Sase do Elena. I vo nego gledam ako najdam pat bez trganje na baricki, go pecatam minimalniot pat. A ako nema takov pat, popolnuvam matrica distance , vo koja gi pisuva distancite do site dostapni polinja. Vo vtoroto bfs, kade shto najverojatno e problemot, pustam bfs od Elena i cuvam distanci vo druga matrica, i taka koga kje najde sosed baricka, so nekoja promenliva maxR=0(na pocetok), go bara maksimumot od maxR, i distancata od S do barickata(dokolku postoi) + distancata od E do barickata +1. I toa na kraj bi trebalo da go dava maksimumot. Kako shto kazav , mislam deka problemot e vo vtoroto bfs, pretpostavuvav deka ne raboti zasto prethodno nemase break, no iako staviv, seushte ne raboti. Zatoa kje zamolam nekoj da mi pomogne so popravka na istiot . (Znaev deka e greskata vo vtoroto BFS, zasto ne pecatese nisto na kraj)
|
|
|
17/12/2018 18:53:36
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Jas go resiv vaka (vo slucajot deka ne moze direktno da se stigne od Sase do Elena):
0) Pustas BFS od Sase, a potoa BFS od Elena. Dvete se na istata dist matrica. Isto taka sakame da znaeme dali nekoe pole e na "stranata na Sase" ili na "stranata na Elena". Ova moze da go napravis ako koristis nekoja druga matrica i stavas na primer sign[r][c] = 'S' ili sign[r][c] = 'E' za vreme na BFSto.
1) Odi kaj sekoe pole sto e baricka. Neka koordinatite se r i c. Sakame da vidime dali ako go izbriseme ova pole ke moze da se stigne od Sase do Elena. Ako moze, sakame da go najdeme najdolgiot pat za toa. Ovoj broj e odgovorot za zadacata. Neka se vika ovoj broj ans. Na pocetok ans = 0.
2) Probaj gi site mozni parovi na sosedni polinja (na pr. (r-1, c) i (r+1, c) za toa nad i pod, ili pak (r-1, c) i (r, c+1) za toa nad i toa desno, i slicno). Na primer neka gi probuvame (r1, c1) = (r-1, c) i (r2, c2) = (r+1, c). Togas ako ovie koordinati ne se baricka, i ako ednoto bilo stignato od Sase, a drugoto od Elena, pravime ans = max(ans, dist[r1][c1] + 1 + dist[r2][c2]). (edinicata vo sredina e deka go pominuvame samoto pole (r, c))
|
|
|
17/12/2018 18:59:13
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
Da, no neli ako pri trganje na sekoja baricka, da barame dali ima pat pomegju niv kje pominuva na vreme. Zatoa jas go resiv vaka, samo baram popravka . Mislam deka sum blisku
|
|
|
18/12/2018 16:34:12
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Ne mozam da razberam sto sakas da napravis, ni vo tekstot ni vo kodot. Ako uspees da go resis na tvojot nacin, super, ama ne znam zosto nekoj bi se macel da ti bara popravka vo kodot?
|
|
|
18/12/2018 23:15:53
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
BATIR wrote:Da, no neli ako pri trganje na sekoja baricka, da barame dali ima pat pomegju niv kje pominuva na vreme. Zatoa jas go resiv vaka, samo baram popravka . Mislam deka sum blisku
Имаше повеќе грешки. (curr.first+dj[i]==ej) наместо (curr.second+dj[i]==ej), не треба +1 кај maxR и слично.
Еве поправен код.
|
|
|
19/12/2018 20:44:14
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
Fala mnogu
|
|
|
|
|
|