Ho scritto l’algoritmo per risolvere ois_lava. Il problema si presenta quando accedo alla matrice per il controllo degli elementi circostanti al blocco vuoto e l’algoritmo, in alcuni casi, esce dalla mappa e perciò mi segnala come errore “Execution killed with signal 11 (could be triggered by violating memory limits)”. Il problema è he non riesco a trovare l’errore!!!
#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;
// dichiaro le variabili per la creazione della matrice
char tile[10000][10000];
int colonne, righe, inizio, fine, counter = 0;
// struttura del grafo
struct nodo {
long min = LONG_MAX;
vector<pair<int,int> > connessi;
};
// creo il grafo che servirà per la soluzione finale
nodo nodi[100000];
int counter_nodo = 1; // counter che servira ad assegnare un valore al nodi
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
in >> righe >> colonne;
// inizializzo le variabili inizio e fine che serviranno per l'algoritmo finale
inizio = 1;
for(int i = 0; i < righe; i++)
{
for(int j = 0; j < colonne; j++)
{
in >> tile[i][j];
if(tile[i][j] == '.')
{
tile[i][j] = counter_nodo;
if(i == righe - 1 && j == colonne - 1)
{
fine = counter_nodo;
break;
}
counter_nodo++;
}
}
}
// avvio il controllo di ogni tassello della mappa
// se è un punto creo un nodo
// altrimenti non faccio nulla
for(int i = 0; i < righe; i++)
{
for(int j = 0; j < colonne; j++)
{
if(tile[i][j] != '#')
{
int y = i;
int x = j;
// verticalmente + 2
if(y < righe - 2)
{
if(tile[y+2][x] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y+2][x];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
// orizzontalmente + 2
if(x < colonne - 2)
{
if(tile[y][x+2] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y][x+2];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
// orizzontalmente
if(x < colonne - 1)
{
if(tile[y][x+1] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y][x+1];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
// diagonalmente (a destra)
if(x < colonne - 1 && y < righe - 1)
{
if(tile[y+1][x+1] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y+1][x+1];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
// diagonalmente (a sinistra)
if(x > 0 && y < righe - 1)
{
if(tile[y+1][x-1] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y+1][x-1];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
// verticalmente
if(y < righe - 1)
{
if(tile[y+1][x] != 35)
{
int a, b;
a = (int)tile[y][x];
b = (int)tile[y+1][x];
nodi[a].connessi.push_back(pair<int,int>(b, 1));
}
}
}
}
}
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);
}
}
}
cout << nodi[fine].min;
}
Come prima cosa ti suggerisco di non crearti il grafo esplicitamente, ma di lavorare direttamente sulla matrice in ingresso, altrimenti rischi di andare fuori tempo limite negli ultimi testcase.
L’errore signal 11 può sì essere causato dalla violazione dei limiti di memoria ma anche dall’accesso a memoria non allocata. Se sei su linux compila con -fsanitize=address e vedi se ti dà errori durante l’esecuzione.
Stai anche attento alla memoria che usi: nel codice crei la matrice tile da 1000010000 = 10^410^4 = 10^8*sizeof(char) byte. Sei molto vicino al limite massimo di memoria di 128MB. Usa una dimensione di 1000, se vuoi essere sicuro di non uscire dalla matrice incrementa questo numero di qualche unità, non di un ordine di grandezza.
Nel codice sottoposto la matrice è grande 1000*1000. Il problema si presenta proprio quando accedo in memoria. Soltanto che non riesco A trovare le condizioni errate nel codice.
Ripeto, prova a utilizzare direttamente la matrice senza crearti il grafo esplicitamente
p.s.: se proprio vuoi usare il grafo (occhio ai tempi di esecuzione) stai attento quando lo crei: nel loop che crea i nodi accedi a tile[y][x], mentre credo che debba essere tile[x][y] ( o tile[x + 1][y], tile[x + 2][y] ecc)
Sempre con una bfs, solo che anziché andare a leggere gli archi da una lista di adiacenza li calcoli basandoti sul nodo / coordinata che hai preso dalla coda
Grazie ancora per chi mi risposto. Volevo chiedere un’ultima cosa. Avendo riscritto l’algoritmo sono riuscito a fare 70/100. L’ultimo problema che mi appare è ‘output non corretto’ nei casi 16 e 17 dell’ultimo subtask.
Questo è il nuovo 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[1000000];
int R, C, counter_nodo = 1;
int tile_int[2000][2000];
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
{
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)
{
// 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));
}
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));
}
// diagonale a destra e a sinistra
if(tile_int[i+1][j+1] != 0)
{
int A = tile_int[i][j];
int B = tile_int[i+1][j+1];
nodi[A].connessi.push_back(pair<int,int>(B, 1));
}
if(tile_int[i-1][j+1] != 0)
{
int A = tile_int[i][j];
int B = tile_int[i-1][j+1];
nodi[A].connessi.push_back(pair<int,int>(B, 1));
}
// salti in orizzontale e verticale
if(tile_int[i][j+2] != 0)
{
int A = tile_int[i][j];
int B = tile_int[i][j+2];
nodi[A].connessi.push_back(pair<int,int>(B, 1));
}
if(tile_int[i+2][j] != 0)
{
int A = tile_int[i][j];
int B = tile_int[i+2][j];
nodi[A].connessi.push_back(pair<int,int>(B, 1));
}
}
}
}
out << dijkstra(1, counter_nodo - 1);
}
P.S: Per chi ha già visto il codice precedente:l’algoritmo non cambia l’unica cosa che ho modificato è il tipo di matrice.
Puoi modificare il messaggio? Così è praticamente illeggibile e alcune parti del codice sono andate perse
La tua soluzione produce output errati perché non consideri tutte le strade possibili: se non vuoi guardare sia a destra che a sinistra, allora devi aggiungere l’arco non solo all’estremità A ma anche all’estremità B, altrimenti il grafo rimane incompleto.
In alternativa, puoi aggiungere i controlli per le direzioni che hai saltato
Secondo me comunque hai scelto un approccio un po’ scomodo, se gestisci i nodi direttamente come coppia di coordinate x e y il codice dovrebbe essere un po’ più semplice
Anche perché anche aggiungendo i salti in entrambe le direzioni, non sono comunque riuscito ad ottenere un punteggio pieno a causa dell’allocazione di troppa memoria in un testcase del subtask 3. Magari puoi trovare anche un altro modo per aggirare il problema, però come ti aveva già suggerito @dp_1 dovresti scegliere di non memorizzare gli archi, agendo implicitamente sulla matrice stessa, calcolando di volta in volta nella funzione djkstra() quali spostamenti puoi fare basandoti sulla posizione (x, y).
