85/100 (teleport)

Il correttore mi da soltanto un output non corretto, ma non riesco a capire dove sia l’errore…

#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <queue>

#define MAX 1000
#define MAX_INT 10000
using namespace std;


int H,W;//Altezza e larghezza
char C[MAX+2][MAX+2];
int sol[MAX+2][MAX+2];
queue<pair<int,int> >coda;
int posXTel,posYTel,posXHouse,posYHouse,xMIN,yMIN,cX,cY;
unsigned int distMin= MAX_INT;
bool teleport = true;
int calcola()
{
	coda.push(pair<int,int>(cY,cX));
	C[cY][cX] = 'v';
	sol[cY][cX] = 0;
	while(!coda.empty())
	{
		pair<int,int> pos = coda.front();
		int righe = pos.first,cols = pos.second;
		coda.pop();
		if(C[righe][cols+1] == '.' && sol[righe][cols]+1<sol[righe][cols+1])
		{
			C[righe][cols+1] = 'v';
			sol[righe][cols+1] = sol[righe][cols]+1;
			coda.push(pair<int,int>(righe,cols+1));
		}else if(C[righe][cols+1] == '@' && sol[righe][cols]+1<sol[righe][cols+1] && teleport == true)
		{
			teleport = false;
			C[righe][cols+1] = 'v';
			sol[righe][cols+1] = sol[righe][cols]+1;
			sol[yMIN][xMIN] = sol[righe][cols+1]+1; 
			coda.push(pair<int,int>(yMIN,xMIN));			
		}else if(C[righe][cols+1] == 'M')
		{
			return sol[righe][cols]+1;
		}
		if(C[righe][cols-1] == '.'  && sol[righe][cols]+1<sol[righe][cols-1])
		{
			C[righe][cols-1] = 'v';
			sol[righe][cols-1] = sol[righe][cols]+1;
			coda.push(pair<int,int>(righe,cols-1));			
		}else if(C[righe][cols-1] == '@' && sol[righe][cols]+1<sol[righe][cols-1] && teleport == true)
		{
			teleport = false;
			C[righe][cols-1] = 'v';
			sol[righe][cols-1] = sol[righe][cols]+1;
			sol[yMIN][xMIN] = sol[righe][cols-1]+1; 
			coda.push(pair<int,int>(yMIN,xMIN));			
		}else if(C[righe][cols-1] == 'M')
		{
			return sol[righe][cols]+1;
		}
		if(C[righe+1][cols] == '.' && sol[righe][cols]+1<sol[righe+1][cols])
		{
			C[righe+1][cols] = 'v';
			sol[righe+1][cols] = sol[righe][cols]+1;
			coda.push(pair<int,int>(righe+1,cols));			
		}else if(C[righe+1][cols] == '@' && sol[righe][cols]+1<sol[righe+1][cols] && teleport == true)
		{
			teleport = false;
			C[righe+1][cols] = 'v';
			sol[righe+1][cols] = sol[righe][cols]+1;
			sol[yMIN][xMIN] = sol[righe+1][cols]+1; 
			coda.push(pair<int,int>(yMIN,xMIN));		
		}else if(C[righe+1][cols] == 'M')
		{
			return sol[righe][cols]+1;
		}
		if(C[righe-1][cols] == '.' && sol[righe][cols]+1<sol[righe-1][cols])
		{
			C[righe-1][cols] = 'v';
			sol[righe-1][cols] = sol[righe][cols]+1;
			coda.push(pair<int,int>(righe-1,cols));			
		}else if(C[righe-1][cols] == '@' && sol[righe][cols]+1<sol[righe-1][cols] && teleport == true)
		{
			teleport = false;
			C[righe-1][cols] = 'v';
			sol[righe-1][cols] = sol[righe][cols]+1;	
			sol[yMIN][xMIN] = sol[righe-1][cols]+1; 
			coda.push(pair<int,int>(yMIN,xMIN));		
		}else if(C[righe-1][cols] == 'M')
		{
			return sol[righe][cols]+1;
		}

	}
	return sol[posYHouse][posXHouse];
}

int main(int argc, char** argv) {
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>H>>W;
	for(int i = 0;i<=H+1;i++)
	{
		for(int j = 0;j<=W+1;j++)
		{
			if((i == 0 || j == 0) || (i == H+1 || j == W+1))
				C[i][j] = '#';
			else
			in>>C[i][j];
		}
	}
	for(int i = 0;i<=H+1;i++)
	{
		for(int j = 0;j<=W+1;j++)
		{
			if(C[i][j] == 'M')
			{
				posYHouse = i;
				posXHouse = j;
			}
			if(C[i][j] == 'C')
			{
				cY = i;
				cX = j;
			}
		}
	}	
	for(int i = 0;i<=H+1;i++)
	{
		for(int j = 0;j<=W+1;j++)
		{
			if(C[i][j] == '@')
			{
				posYTel = i;
				posXTel = j;
				if(distMin > sqrt(pow((posYHouse-posYTel),2)+pow((posXHouse-posXTel),2)))
				{
					distMin = sqrt(pow((posYHouse-posYTel),2)+pow((posXHouse-posXTel),2));
					yMIN = i;
					xMIN = j;
				}	
			}
		}
	}

	
	for(int i = 0;i<= H+1;i++)
	{
		for(int j = 0;j<=W+1;j++)
		{
			sol[i][j] = MAX_INT;
		}
	}
	
	out<<calcola();

	return 0;
}

Questo loop non mi convince troppo… stai cercando il teletrasporto più vicino vero? Considera che la distanza non è cartesiana, ma per calcolare la distanza effettiva al teletrasporto più vicino devi lavorare sul grafo, per come è ora il codice questa ricerca ignora eventuali ostacoli. Ad esempio se la griglia fosse di questo tipo:

4 4
@...
####
C..@
###M

Finiresti per scegliere il teletrasporto in alto a sinistra (d = 2), che però è irraggiungibile.

Ho provato il tuo codice su questo input e ritorna 5, mentre la soluzione corretta è 4.

Dario

1 Mi Piace

Graie dell’aiuto, ma non riesco a capire come lavorare sul grafo per avere la distanza minima tra la casa e il teletrasporto.

Puoi usare un altro bfs, partendo dalla fine

Cioè devo andare a cercare la distanza minima che c’è tra la M e ogni @ presente sulla matrice per poi prendere la distanza minima tra tutte quante?

Se trovi il teletrasporto più vicino a M sai che dovrai sempre teletrasportarti lì:


Qui William l’ha spiegato :slight_smile:

Si, questo mi è chiaro, non mi è chiaro come calcolare qual’è il teletrasporto speciale inizialmente.
Potrei usare una bfs e partire da M, andandomi a cercare la distanza minima tra M e il teletrasporto, ma non so qual’è il teletrasporto, cioè non so quale sia il punto di destinazione, quindi dovrei andare a calcolare la distanza minima tra la M e ogni teletrasporto presente per poi prendere la distanza minima tra tutte le distanze.

Non ti serve sapere qual è, ti basta sapere la distanza del teletrasporto più vicino perché tanto avrai già il percorso minimo tra il teletrasporto ed M.
Una volta che hai la distanza tra il teletrasporto ed M devi vedere se vale la pena usarlo o ci si può arrivare senza, ad M.