Editorial for Sahovska trka
Submitting an official solution before solving the problem yourself is a bannable offence.
Rešenje zadatka Šahovska trka.
Glavna ideja je da se napravi graf od čvorova gde svaka pozicija na tabli ima po 5 čvorova (jedan za svaku figuru). Grane u ovom grafu predstavljaju sve poteze koje možemo da napravimo i imaju težinu od 1 do 5. Kako bi izbegli , ove grane ne treba da čuvamo u memoriji nego da prođemo kroz njih iterativno kada posmatramo neki čvor. Jedno od rešenja pušta algoritam\( na ovom grafu kako bi se našla udaljenost svih čvorova od črvora koji predstavlja kralja na poziciji \)(1,1)\(. Kako bi ubrzali algoritam, tokom prolaženja kroz sva polja na koja može kraljica/top/lovac da ode u nekom smeru, pored uslova da se prekine pretraga kada se stigne na blokirano polje, treba uvesti uslov da se prekine pretraga ako se stigne na polje koje ima istu ili manju udaljenost od udaljenosti trenutnog polja (ne računajući trenutno polje). Vremenska složenost: \)O(n^3 * log n)\(, Memorijska složenost: \)O(n^2)\(. Još jedna optimizacija programa koja nije bila potrebna za \)100Dijkstrinog pusti algoritam\(. Vremenska složenost: \)O(n^3)\(, Memorijska složenost: \)O(n^2)~.
Comments