[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Zadaca Ljubov  XML
Forum Index » Задачи од национални натпревари
Author Message
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)
VlatkoSh


[Avatar]

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))
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
VlatkoSh


[Avatar]

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?
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 и слично.

Еве поправен код.
BATIR



Joined: 20/06/2015 16:36:50
Messages: 155
Offline

Fala mnogu
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team