Snažím sa implementovať algoritmus Dijkstra s cieľom nájsť najkratšiu cestu medzi dvoma bodmi v mriežke (x, y), ale problémom je, že sa môžem pohybovať len hore, dole, vpravo a vľavo.
Mám ArrayList obsahujúci čísla x a ybody, ktoré potrebujem odovzdať a iný zoznam ArrayList bodov, ktoré sú prekážkami na mriežke, sa snažím napísať funkciu, ktorá vráti ArrayList o pohybe potrebnom na dokončenie celej cesty.
Napríklad: 1, 1, 2, 3, 4, 1, 1 je pravý 2, ktorý zostáva a 3 je hore a nakoniec 4 je nadol.
Môžete mi poskytnúť niekoľko tipov a / alebo príkladov.
odpovede:
2 pre odpoveď č. 1Po prvé, vieme, že algoritmus spoločnosti Dijkstra je pre tradične vážené grafy. Mohol ešte pracovať s jednotkovými okrajmi (všetka hmotnosť 1), ale nemusí to byť najefektívnejšie riešenie.
V oboch prípadoch, podľa toho, ktorý algoritmus použijete, budetepotrebujete zaobchádzať s vašou mriežkou ako graf. Aby ste to urobili, vytvorte súpravu okrajov. Ak nie sú žiadne obmedzenia nad "žiadne uhlopriečky", vaše hrany budú spojením medzi každým bodom a jeho susedmi nad, pod a vedľa neho. Na grafe môžete potom pracovať tak, že sa presuniete cez hrany a body na grafe.