Allego la traccia dell'esercizio su cui ho problemi...mi date una mano per iniziare a impostarlo almeno?!
ho pensato di fare un qualcosa tipo:
scorro la matrice, ad ogni passo guardo avanti a sinistra e a destra della cella... se è diversa da 0 (zero - che sarebbe il muro del labirinto) vado avanti fino ad arrivare ad uno dei 4 bordi..poi però dovrei restituire la posizione di entrata e uscita...e non so come fare!
Sei sulla buona strada, il tuo problema è sostanzialmente lo stesso del floodfill (lo strumento riempimento dei programmi di grafica), del cui algoritmo trovi facilmente esempi in giro; in particolare puoi implementare una soluzione ricorsiva in maniera molto semplice (anche se a rischio stack overflow in caso di labirinti immensi).
(tra parentesi, l'immagine è troppo piccola e risulta illeggibile)
Amaro C++, il gusto pieno dell'undefined behavior.
Ho caricato la traccia su: http://depositfiles.com/files/hkvw7h2bt
qua si vede meglio: http://depositfiles.com/files/nxlow8eh3Originariamente inviato da mistergks
Ho caricato la traccia su: http://depositfiles.com/files/hkvw7h2bt
... e così si vede anche senza dover lottare contro depositfiles...
Amaro C++, il gusto pieno dell'undefined behavior.
Scusa ma la posizione di entrata è il punto dal quale parti.Originariamente inviato da mistergks però dovrei restituire la posizione di entrata e uscita...e non so come fare!
Io partirei sempre dalla prima colonna e la scorrerei fino ad incontrare un numero diverso da 0, se non ce ne sono, invece scorri la prima riga! Altrimenti continui: ultima colonna o ultima riga: una delle quattro deve per forza contenere un ingresso. Mentre scorri usi un intero e lo incrementi, in questo modo conoscerai la posizione di partenza.
Per quanto riguarda la posizione di uscita è la stessa cosa: usi una coppia di interi che inizialmente è l'ingresso, e man mano che il tuo algoritmo si ripete aggiorna questa coppia di numeri, il suo ultimo valore sarà la posizione di uscita (quando la riga o la colonna equivalgono ad una riga/colonna della matrice che sta sul bordo).
Edit:
Dato che gli ingressi possono essere molteplici, potresti contarli e salvarli tutti e far ripetere l'algoritmo per ognuno di essi finchè non ne trovi uno che raggiunge un bordo
Io procederei così:
- esamini tutto il bordo, alla ricerca di un uno;
- quando becchi un uno, fai partire una procedura ricorsiva su quella posizione di partenza, che ad ogni step di ricorsione si "guarda attorno" cercando il numero successivo; se raggiunge qualcosa (arriva ad un bordo) restituisce la posizione finale, se arriva ad un vicolo cieco restituisce un qualche flag (ad esempio una posizione non valida);
- il programma termina quando si è esaminato tutto il bordo o quando la procedura ricorsiva ha fornito una posizione finale valida.
Amaro C++, il gusto pieno dell'undefined behavior.
non di un uno ma di un qualsiasi numero diverso da 0Originariamente inviato da MItaly
Io procederei così:
- esamini tutto il bordo, alla ricerca di un uno;
[...]piccola svista.
Comunque ottima idea quella del fa tornare la posizione, si può far ripetere la funzione finchè il dato restituito è un bordo o è invalido(per esempio -1,-1). Mi piace.
Poi se la posizione era valida esci dal loop, altrimenti parti da un altro ingresso (se c'è)
Se però è diverso da uno devi richiamare la funzione ricorsiva in modo che proceda cercando i numeri in verso discendente.Originariamente inviato da MegaAlchimista
non di un uno ma di un qualsiasi numero diverso da 0
Amaro C++, il gusto pieno dell'undefined behavior.
Come lo imposteresti se invece i bivi ci fossero? Se a metà strada si trovasse di fronte a due o tre possibilità?
Permessi di invio
Rispondi quotando