Qualcuno è riuscito a ottenere 100 punti in questo problema?
Io mi fermo a 90 perché due richieste della subtask 4 mi escono fuori tempo massimo.
Uso un vettore dinamico in cui salvo le “mosse” del robot (struct in cui ho incluso riga, colonna, orientamento) e partendo dall’ultima mossa effettuata faccio scorrere il vettore dal fondo per verificare la presenza di una mossa uguale.
Grazie mille in anticipo
Se ho capito bene, ogni volta che fai una mossa e capiti in una casella con un certo orientamento cerchi (nel tuo vettore dei “salvataggi”) se sei già capitato in una situazione uguale.
Facendo delle stime molto “larghe”, per fare questa ricerca impieghi tempo lineare nella lunghezza del vettore e lo fai per tante volte quante sono tutte le possibili situazioni in cui ti puoi trovare: alla peggio quindi hai un qualcosa come O(NM)\times O(NM) = O((NM)^2) che è una complessità un po’ troppo alta per questo problema.
Al posto di usare un vettore in cui ti salvi le situazioni precedenti (in cui è necessario scorrerle tutte) riesci a pensare ad una soluzione più “diretta” che ti permetta un tempo costante per questo tipo di verifica?
Hint: pensa al problema come ad un grafo
Devo dire che avevo pensato a qualsiasi tipo di soluzione tranne che al grafo.
Ora appena ho tempo provo a implementarlo
Grazie mille