[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задачи со пронаоѓање пат.  XML
Forum Index » Задачи од национални натпревари
Author Message
ThePopivanov



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

Здраво може некој да ми помогне околу овој вид на задачи? Барам на интернет но неможам да најдам :/
Еве задачи од овој вид.

http://mendo.mk/Task.do?id=704
http://mendo.mk/Task.do?id=629

И исто така задачата од регионалниот натпревар минатата година на која сеуште не го знам одговорот. http://mendo.mk/Task.do?id=614
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

Вакви задачи се сведуваат на пребарување низ графови и обично се решаваат со BFS (Breadth-First Search) или DFS (Depth-first Search). Сите задачи што ги посочи се решаваат со овој алгоритам, но секако со мали модификации за дадениот проблем.
Задачата Градинар се сведува на откривање на она поле кое може да биде достигнато од најголем број на цвеќиња.
Љубов е многу слична како Градинар, се сведува на наоѓање на ѕидот P за кого збирот од должината на најкраткиот пат од Сашо до P и најкраткиот пат од Елена до P е најголем.
За Чоколадна коцка, проблемот го сведуваме на наоѓање на максималната длабочина на пребарување до која можеме да стигнеме, и колку елементи (коцки) имаме на таа длабочина.
ThePopivanov



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

Може некој пример
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

https://www.e-olymp.com/en/problems/1064
https://www.e-olymp.com/en/problems/1060

Еве многу едноставни примери што се решаваат без некои потешкотии. На CodeFu имаш десетици вакви задачи, можеш да ги побараш и таму.

This message was edited 1 time. Last update was at 23/03/2017 16:54:00

stoki97



Joined: 18/02/2015 15:20:59
Messages: 9
Offline

Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.


Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red



despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

stoki97 wrote: Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.


Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red



Најверојатно користењето на map ти е проблемот. Map структурата во C++ е имплементирана како бинарно пребарувачко дрво, па секое запишување/пребарување го извршува во O(logN) време во најдобар случај. Ако ја смениш map структурата со обична матрица многу ќе ги убрзаш овие операции, односно ќе станат O(1).
stoki97



Joined: 18/02/2015 15:20:59
Messages: 9
Offline

Probav so matrica ama na dump pagja neznam zosto eve go kodot.

despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

stoki97 wrote:Probav so matrica ama na dump pagja neznam zosto eve go kodot.


Грешката ти е во оваа линија код:


Проверката дали координатите влегуваат во границите ја правиш откако пробуваш да го прочиташ полето од матрицата, па затоа добиваш и runtime error. Оваа линија се јавува во bfs и во bfs2 процедурата. Стави ги проверките за координатите на почеток и би требало да работи.

This message was edited 1 time. Last update was at 02/04/2017 12:17:43

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