The floor is lava

Aiuto
1

Ho risolto il problema in maniera ricorsiva, e provando i due input di esempio in locale, il codice sembra funzionare, ma quando mando la sottoposizione mi da un errore in tutti gli output compresi quelli di esempio. L’errore è: Execution killed with signal 11 (could be triggered by violating memory limits). Il codice è questo :

#include <iostream>
#include <fstream>
#define MAX 10000

int m[MAX][MAX];
int h,w;
using namespace std;

void percorso(int i,int j)
{
    for(int x = -2;x<3;x++)
    {
        for(int y = -2;y<3;y++)
        {
            if(i+x<0|| j+y<0||i+x>h-1||j+y>w-1);
            else if(m[i+x][j+y] == 0 || m[i+x][j+y] > m[i][j]+1 && (i+x >= 2 && j+y >= 2))
            {
                m[i+x][j+y] = m[i][j]+1;
                percorso(x+i,j+y);
            }else if(m[i+x][j+y] == 0 || m[i+x][j+y] > m[i][j]+1 && (i+x == j+y))
            {
                m[i+x][j+y] = m[i][j]+1;
                percorso(x+i,j+y);
            }else if(m[i+x][j+y] == 0 || m[i+x][j+y] > m[i][j]+1 && (i+x < 2 && j+y < 2))
            {
                m[i+x][j+y] = m[i][j]+1;
                percorso(x+i,j+y);
            }
        }
    }
}
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>h;
    in>>w;
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            char c;
            in>>c;
            if(c == '.')
                m[i][j] = 0;
            else
                m[i][j] = -1;
        }

    }
    percorso(0,0);
    cout <<m[h-1][w-1];
    return 0;
}
2

Prova a spiegare come funziona il tuo algoritmo: anche se non è importante in questo caso almeno ci si capisce un po’ di più di quello che hai scritto :sweat_smile:
In ogni caso errori del genere vengono fuori quando si legge/scrive dove non si dovrebbe (tipicamente si va a guardare una posizione fuori dai limiti di un array), oppure quando si usa troppa memoria (o comunque se ne tenta di allocare troppa).

Intanto una cosa che ti può far risparmiare un po’ di memoria è diminuire MAX: nelle assunzioni si dice che la matrice può essere massimo 1000*1000 (non credo che l’errore sia questo, ma comunque conviene sempre evitare sprechi di memoria). :wink:

P.S: alcune parti del codice sono parecchio contorte, ad esempio questo if:

Credo di aver capito a cosa serva, ma prova a trovare un altro metodo per farlo, questo non è il massimo a mio parere.

EDIT: Ho notato adesso che alla fine hai usato lo standard output invece dell’output su file :grin:

3

Si, ho scritto il codice in fretta e furia e molte cose sono abbastanza contorte… per quanto riguarda lo standard output l’ho usato solo per debuggare il codice senza dover andare a vedere ogni volta nel file di output… volevo sapere anche se questo ripo di problema poteva essere risolto con la ricorsione, in quanto è esponenziale a quanto pare

4

Dunque, sicuramente 100 punti con la ricorsione non li otterresti, dato che come hai detto tu andrebbe fuori tempo.
Tuttavia secondo me si può risolvere anche con la programmazione dinamica (e quindi ricorsione con memoizzazione nel caso della top-down), guardando il problema mi era venuta in mente sia questa soluzione che quella con i grafi.

Per quanto riguarda quell’errore, mi viene da dire che sia causato da quel MAX, anche perchè mi pare che gli indici non vadano mai fuori dai limiti.

5

Ricompilalo con -fsanitize=address e vedi se ti dà qualche errore in esecuzione. Se te li dà è perchè accedi a memoria non allocata.

Dario

1 Mi Piace
6

Stai allocando una matrice m costituita da 10^4 \cdot 10^4 = 10^8 interi. Questo significa che stai allocando circa 10^8 \cdot 4 byte, ovvero circa 400 MB: decisamente troppo.
È sufficiente definire MAX 1000, il numero massimo per H, W previsto dalle assunzioni del problema. Se il tuo intento era evitare “off-by-one error” puoi aumentare tale valore di qualche unità, ma non di un ordine di grandezza!

1 Mi Piace