Problema LAVA (35/100)

Aiuto
1

Ciao ragazzi, il problema lava mi continua a dare 35/100 e non capisco dove sia il problema…
Ho lavorato su una matrice implicita senza crearmi un grafo, quindi lavorando solo con i nodi( o coordinate della matrice) che erano dentro la coda. Ho controllato tutto le varie direzioni… e per praticità ho cerchiato la matrice da # (lava).
Ecco qui il codice:

 #include <iostream>
 #include <fstream>
 #include <queue>
 #include <stack>
 #include <list>
 #include <utility>

 #define MAX 1000

using namespace std;

char tiles[MAX+10][MAX+10];
char sol[MAX+10][MAX+10];
queue<pair<int,int> >coda;
int H,W; 


int calcola(void)
{
	coda.push(pair<int,int>(2,2));
    tiles[2][2] = 'v'; // La lettera V sta per visto 
	sol[2][2] = 0; // L'indice 2 2 sta per il primo nodo (elemeto) della matrice 
	//è settato a 0 perché è la posizione di partenza
	
	while(!coda.empty())
	{
		//Nodo
		pair<int,int>pos = coda.front();
		int righe = pos.first, cols = pos.second;
		coda.pop();
          			//Diagonle a destra in basso
  					if(tiles[righe+1][cols+1] == '.')
					{
						if(righe+1 == H+1 && cols+1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe+1][cols+1] = 'v';
						sol[righe+1][cols+1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe+1,cols+1));
					}
					//Diagonale a sinistra in alto
					if(tiles[righe-1][cols-1] == '.')
					{
						if(righe-1 == H+1 && cols-1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe-1][cols-1] = 'v';
						sol[righe-1][cols-1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe-1,cols-1));
					}
					//Diagonale a sinistra in basso  
					if(tiles[righe+1][cols-1] == '.')
					{
						if(righe+1 == H+1 && cols-1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe+1][cols-1] = 'v';
						sol[righe+1][cols-1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe+1,cols-1));
					}   
					//Diagonale a destra in alto
					if(tiles[righe-1][cols+1] == '.')
					{
						if(righe-1 == H+1 && cols+1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe-1][cols+1] = 'v';
						sol[righe-1][cols+1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe-1,cols+1));
					}        
					//Super jump (verticale)
					if(tiles[righe-2][cols] == '.')
					{
						if(righe-2 == H+1 && cols == W+1)
							return sol[righe][cols]+1;
						tiles[righe-2][cols] = 'v';
						sol[righe-2][cols] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe-2,cols));
					}
					//Super jump (orizzontale)
					if(tiles[righe+2][cols] == '.')
					{
						if(righe+2 == H+1 && cols == W+1)
							return sol[righe][cols]+1;
						tiles[righe+2][cols] = 'v';
						sol[righe+2][cols] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe+2,cols));
					}  
					//Verticale   in basso
					if(tiles[righe+1][cols] == '.')
					{
						if(righe+1 == H+1 && cols == W+1)
							return sol[righe][cols]+1;
						tiles[righe+1][cols] = 'v';
						sol[righe+1][cols] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe+1,cols));
					}
					//Verticale in alto
					if(tiles[righe-1][cols] == '.')
					{
						if(righe-1 == H+1 && cols == W+1)
							return sol[righe][cols]+1;
						tiles[righe-1][cols] = 'v';
						sol[righe-1][cols] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe-1,cols));
					}    
					//super jump (orizzontale a sinistra)
					if(tiles[righe][cols+2] == '.')
					{
						if(righe== H+1 && cols+2 == W+1)
							return sol[righe][cols]+1;
						tiles[righe][cols+2] = 'v';
						sol[righe][cols+2] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe,cols+2));
					}      
					//super jump (orizzontale a destra)	
					if(tiles[righe][cols-2] == '.')
					{
						if(righe== H+1 && cols-2 == W+1)
							return sol[righe][cols]+1;
						tiles[righe][cols-2] = 'v';
						sol[righe][cols-2] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe,cols-2));
					} 	  
					//Orizzontale a destra  
					if(tiles[righe][cols+1] == '.')
					{
						if(righe == H+1 && cols+1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe][cols+1] = 'v';
						sol[righe][cols+1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe,cols+1));
					}     
					//Orizzontale a sinistra 	
					if(tiles[righe][cols-1] == '.')
					{
						if(righe == H+1 && cols-1 == W+1)
							return sol[righe][cols]+1;
						tiles[righe][cols-1] = 'v';
						sol[righe][cols-1] = sol[righe][cols]+1;
						coda.push(pair<int,int>(righe,cols-1));
					} 	       			
            }
    
	return sol[H+1][W+1];//H+1 E W+1 E' l'ultimo elemento della matrice 
}

int main(int argc, char** argv) {
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	//Per praticità la matrice è cerchiata da # per ben 2 volte
	//2 volte soltanto perché c'è la possibilità di fare un super salto e quindi di controllare un elemento in due caselle dopo.
	in>>H>>W;
	for(int i = 0; i<=H+3; i++)
	{
		for(int j = 0; j<=W+3; j++)
		{
			if((i == 0 || j == 0) || (i == H+3 || j == W+3))
				 tiles[i][j]= '#';
			else if((i == 1 || j == 1) || (i == H+2 || j == W+2))
				 tiles[i][j]= '#';
			else
				in>>tiles[i][j];
		}
	}
	cout<<calcola();
	return 0;}
2

Che errore ottieni dal correttore nei casi che non funzionano?

Se non sbaglio, quando aggiungi un nuovo nodo da visitare alla coda controlli solo se quella casella è visitabile, non se hai già trovato una distanza migliore che ci passa. Prova a controllare, prima di aggiungere una casella alla coda, se per quella casella hai già trovato un percorso migliore. Continua con quella casella solo se il percorso che stai considerando in quel momento è più corto dei percorsi già esistenti fino a quella casella.

Spero di essermi spiegato bene, se ti serve altro chiedi pure.

Dario

1 Mi Piace
3

Quindi nei vari controlli potrei mettere ad esempio:

if(tiles[righe+1][cols+1] == '.' || sol[righe][cols]+1 < sol[righe+1][cols+1])
{....}

Sono ancora alle prime armi quindi scusami se ho scritto una stupidaggine…

4

Direi più
if(tiles[righe + 1][cols + 1] == '.' && sol[righe][cols] + 1 < sol[righe + 1][cols + 1])

Con || fai un OR logico, quindi basta che una delle due condizioni sia vera per rendere vero il tutto, con && fai un AND logico, così entrambe le condizioni devono essere verificate.

p.s. Quale errore ottieni dal correttore?

1 Mi Piace
5

Inizialmente anche io ho pensato subito di usare l’and, perché come hai detto tu era più logico, ma mi da 0/100,nemmeo un output corretto…

6

Nei casi di esempio come output mi da 0

7

Credo che devi inizializzare ogni elemento della matrice sol con un valore alto (tipo il classico INT_MAX / 2) invece che lasciarla inizializzata a zero come succede di default con le variabili globali.

2 Mi Piace
8

Grazie per il consiglio, mi ha dato 70/100 , gli ultimi 2 outputs sono incorretti

9

Prova a dichiarare sol come matrice di int invece che di char, per come è ora se la distanza è maggiore di 255 va in overflow.

2 Mi Piace
10

già fatto, mi ero accorto di averlo dichiarato char appena 10 minuti fa

11

Ho risolto, ho inizializzato la matrice sol ad un valore più alto di 1000 e mi ha dato 100/100

12

In generale è meglio inizializzare ad un valore molto più alto di quello che ti serve, per quello ti suggerivo INT_MAX / 2, che va bene praticamente ovunque.

Dario

2 Mi Piace