# Problema LAVA (35/100)

**URL:** <https://forum.olinfo.it/t/problema-lava-35-100/4214>\
**Category:** Aiuto\
**Created:** [11 Dicembre 2016, 2:54pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214 "2016-12-11T14:54:58Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 2:54pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/1 "2016-12-11T14:54:59Z")

</div>

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;}
```

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Dicembre 2016, 6:52pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/2 "2016-12-11T18:52:18Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:12pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/3 "2016-12-11T19:12:05Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Dicembre 2016, 7:22pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/4 "2016-12-11T19:22:17Z")

</div>

> [@Keyword](#):
>
> if(tiles[righe+1][cols+1] == ‘.’ || sol[righe][cols]+1 \< sol[righe+1][cols+1])

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?

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:25pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/5 "2016-12-11T19:25:30Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:26pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/6 "2016-12-11T19:26:37Z")

</div>

Nei casi di esempio come output mi da 0

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Dicembre 2016, 7:29pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/7 "2016-12-11T19:29:19Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:35pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/8 "2016-12-11T19:35:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Dicembre 2016, 7:38pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/9 "2016-12-11T19:38:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:40pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/10 "2016-12-11T19:40:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\
**Post date:** [11 Dicembre 2016, 7:49pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/11 "2016-12-11T19:49:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Dicembre 2016, 7:52pm UTC](https://forum.olinfo.it/t/problema-lava-35-100/4214/12 "2016-12-11T19:52:12Z")

</div>

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