Salve vi volevo chiedere consigli su quale algoritmo utilizzare per la risoluzione del problema sottoposto ieri 29/11/2016 alle OIS. Volevo anche chiedere come era possibile effettuare una BFS direttamente su una matrice come quella presa da input nel suddetto problema.
Grazie
L’algoritmo da usare è proprio la BFS (pensaci su come usarla). La puoi usare senza creare un grafo semplicemente muovendo le coordinate (x, y) intorno ad una cella e pushando le 4 posizioni come una coppia di numeri (ovviamente non sono sempre 4 le posizioni controlla di non andare fuori matrice o in una cella non valida per il problema).
Come si potrebbero gestire le macchine del teletrasporto?
Non riesco a trovare delle soluzioni concrete 
Un modo è questo: ogni volta che si incontra una cella di teletrasporto, invece dei “soliti” 4 vicini, ci saranno 4 vicini più tutte le altre celle di teletrasporto esistenti (è necessario quindi aggiungere un ciclo for per iterare sui vicini “aggiuntivi”… magari due cicli for nidificati).
Questo può essere lento nel caso in cui ci siano tanti teletrasporti (ogni volta che capiti in uno ti tocca aggiungere un sacco di cose in coda), per cui è possibile pensare a un’ottimizzazione… Una volta che si entra in un teletrasporto, c’è solo uno tra gli altri teletrasporti che ha senso mettere in coda assieme ai “soliti” 4 vicini. Si può calcolare inizialmente qual è questo teletrasporto speciale, e poi ogni volta che si visita una cella di teletrasporto si aggiungono i 4 “soliti” vicini + la cella di teletrasporto speciale.
Salve a tutti, dopo un po’ di studio con questo codice riesco a prendere 45 punti ma per i casi che non tornano mi da “Execution killed with signal 11 (could be triggered by violating memory limits)”.
Qualcuno mi può aiutare?
Codice: http://pastebin.com/uWW46fYS
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
Non dovrebbe essere int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; ?
1 Mi Piace
Funziona lo stesso, notate altri problemi?