Problema: ois_teleport

Aiuto
1

Come con lava ho avuto un problema sia in gara che tutt’ora con il problema teleport. L’idea che ho applicato è quella di creare un grafo diretto e di applicare l’algoritmo di dijkstra. Il problema che sorge è che mi esci dalla memoria e non saprei dove.
Questo è il codice:

 #include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>
#include <fstream>

using namespace std;

struct nodo {
    long min = LONG_MAX;
    vector<pair<int,int>> connessi;
};

nodo nodi[1000001];
int R, C, counter_nodo = 1;
int tile_int[2000][2000];
int teletrasporti[1000000];
int counter_teletrasporti = 0;
int inizio, fine;
char temp;

int dijkstra(int inizio, int fine)
{
    nodi[inizio].min = 0;
    queue<int> coda;
 
    coda.push(inizio);
    while (!coda.empty()) 
	{
        int attuale = coda.front();
        coda.pop();
 
        for (auto i: nodi[attuale].connessi)
		{
			if (i.second + nodi[attuale].min < nodi[i.first].min) 
			{
				nodi[i.first].min = i.second + nodi[attuale].min;
				coda.push(i.first);
			}
		}
    }
 
	return nodi[fine].min;
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	in >> R >> C;
		
	for(int i = 1; i <= R; i++)
	{
		for(int j = 1; j <= C; j++)
		{
			in >> temp;
			if(temp == '.')
			{
				tile_int[i][j] = counter_nodo;
				counter_nodo++;
			}
			else if(temp == 'C')
			{
				inizio = counter_nodo;
				tile_int[i][j] = counter_nodo;
				counter_nodo++;
			}
			else if(temp == 'M')
			{
				fine = counter_nodo;
				tile_int[i][j] = counter_nodo;
				counter_nodo++;
			}
			else if(temp == '@')
			{
				teletrasporti[counter_teletrasporti] = counter_nodo;
				tile_int[i][j] = counter_nodo;
				counter_teletrasporti++;
				counter_nodo++;
			}

			else
			{
				tile_int[i][j] = 0;
			}
		}
	}
	
	for(int i = 1; i <= R; i++)
	{
		for(int j = 1; j <= C; j++)
		{
			if(tile_int[i][j] != 0)
			{
			    if(j < C)
			    {
    				// movimenti orizzontali e verticali
    				if(tile_int[i][j+1] != 0)
    				{
    					int A = tile_int[i][j];
    					int B = tile_int[i][j+1];
    
    			        nodi[A].connessi.push_back(pair<int,int>(B, 1));
    			        nodi[B].connessi.push_back(pair<int,int>(A, 1));
    				}
			    }
			    
				if(i < R)
				{
    				if(tile_int[i+1][j] != 0)
    				{
    					int A = tile_int[i][j];
    					int B = tile_int[i+1][j];
    
    			        nodi[A].connessi.push_back(pair<int,int>(B, 1));
    			        nodi[B].connessi.push_back(pair<int,int>(A, 1));
    				}
				}
			}
		}
	}

	for(int i = 0; i < counter_teletrasporti; i++)
	{
		int A = teletrasporti[i];
		for(int j = 0; j < counter_teletrasporti; j++)
        {
            if(i == j)
                continue;
		    int B = teletrasporti[j];

	        nodi[A].connessi.push_back(pair<int,int>(B, 1));
	        nodi[B].connessi.push_back(pair<int,int>(A, 1));
        }
	}
	
	out << dijkstra(inizio, fine);
}
2

Quando lavori su una matrice crearti esplicitamente il grafo è una cosa da evitare il più possibile: invece di salvarti gli archi puoi modificare la funzione dijkstra per lavorare direttamente sulla matrice, cercando i vicini sulla base dei caratteri nelle celle adiacenti a quella corrente. Ovviamente in questo modo non considereresti i teletrasporti, ma puoi lavorarci facilmente dopo la (le?) visita.

Dario

1 Mi Piace
3

Per quanto riguarda la memoria, considera che stai lavorando su al più 10^6 caselle, e ognuna può avere fino a quattro vicini (per ora ignoriamo i teletrasporti). Salvando ogni arco come coppia di interi utilizzi nel caso peggiore
10^6 * 4 * 8 = 32 * 10^6 byte
Contando i teletrasporti la cosa peggiora: ci possono essere al più 10^6 teletrasporti, e ognuno è collegato da un arco bidirezionale a tutti gli altri. Questo vuol dire un consumo di memoria nel caso peggiore di
10^6 * (10^6 - 1) * 8 = 8 * 10^12 byte
circa 125000 volte più grande del limite di memoria del problema.

1 Mi Piace
4

Grazie. Più che altro volevo sapere se era possibile diminuire l’occupazione della memoria.

5

Si, non mantenendo gli archi esplicitamente

2 Mi Piace