Problema "minato"

Scusate per la domanda su un esercizio abbastanza banale, ma provando a farlo in dinamica sto riscontrando qualche problema. Cioè la mia idea era quella di usare due matrici, una di caratteri che hanno tutto il campo, e l’altra di interi dove la prima riga e la prima colonna sono riempiti di 1 (e di 0 dove ci sono i ‘+’) e nella posizione (i, j) (con 0 < i < N e 0 < j < M) vi sia il risultato della somma di (i-1, j) e (i, j-1).

Il codice è questo (5/100pt):

using namespace std;

int N, M;
char mat[100][100];
int sol[100][100];

int main(){
    ifstream in("input.txt");
    in >> N >> M;
    in.ignore(1);

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            in >> mat[i][j];
    in.close();

    for(int i=0; i<=M; i++)
        if(mat[0][i]!='+')
            sol[0][i] = 1;
    for(int i=0; i<=N; i++)
        if(mat[i][0]!='+')
            sol[i][0] = 1;


    for(int i=1; i<N; i++)
        for(int j=1; j<M; j++)
            if(mat[i][j] != '+')
                sol[i][j] = sol[i-1][j] + sol[i][j-1] + sol[i-1][j-1];

    ofstream out("output.txt");
    out << sol[N-1][M-1] << "\n";
    out.close();
    return 0;
}
So che si può risolvere anche senza dinamica, però voglio capire perché quest'algoritmo non funziona.

Scusate ho sbagliato a postare il codice, avevo fatto una prova giusto per vedere come andava. Quello corretto è questo:

#include <fstream>
using namespace std;

int N, M;
char mat[100][100];
int sol[100][100];

int main(){
    ifstream in("input.txt");
    in >> N >> M;
    in.ignore(1);

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            in >> mat[i][j];
    in.close();

    for(int i=0; i<=M; i++)
        if(mat[0][i]!='+')
            sol[0][i] = 1;
    for(int i=0; i<=N; i++)
        if(mat[i][0]!='+')
            sol[i][0] = 1;


    for(int i=1; i<N; i++)
        for(int j=1; j<M; j++)
            if(mat[i][j] != '+')
                sol[i][j] = sol[i-1][j] + sol[i][j-1];

    ofstream out("output.txt");
    out << sol[N-1][M-1] << "\n";
    out.close();
    return 0;
}

Ed inoltre dimenticavo di specificare che in ogni posizione (i, j) della matrice sol c'è il numero di percorsi diversi che Topolino può seguire per arrivare a quel punto.

Mi sembra che tu abbia risolto una versione diversa del problema, dove topolino può partire da un punto qualsiasi, che però stia o sul bordo sinistro o sul bordo “in alto”.

Prova ad esempio questo caso di test che dovrebbe dare 0… lasciamo perdere per adesso il fatto che il testo garantisce che la risposta sia almeno 1 :stuck_out_tongue:

3 2
*+
++
**

Hai ragione. Sapevo che era un problema banale ahahah cioè io ero partito dal presupposto che ogni lastrone presente sul bordo potesse essere raggiunto con un solo percorso, a patto che questo non fosse un lastrone trabocchetto. Invece, giustamente, appena trova un lastrone con trabocchetto non può più raggiungere quelli in basso/a sinistra.
Grazie :slight_smile:

In realtà puoi anche evitare del tutto di inizializzare i bordi: ti basta sapere che hai 1 modo di arrivare in (1, 1). Tutti gli altri modi li costruisci per conseguenza di quel singolo modo…

In questa maniera nella tua soluzione da 100/100 sparirebbero le righe 17-22, sostituite da una singola inizializzazione :slight_smile:
E dovresti adattare un po’ il ciclo che aggiorna la matrice (in particolare gli indici iniziali), e aggiungere qualcosa del tipo:

if (i > 0) sol[i][j] += sol[i-1][j];
if (j > 0) sol[i][j] += sol[i][j-1];

Sì sì lo so che si poteva fare così. Ma ho scritto il codice di getto e la prima soluzione che mi è venuta in mente era quella. Poi non mi funzionava e mi sono incaponito con quella, perché in fin dei conti era corretta e non capivo perché continuava a darmi 5/100.
Scusa se approfitto, ma senza aprire un nuovo topic ti chiedo qui direttamente. La funzione next_permutation procede in ordine lessicografico giusto? Perché ho problemi anche con “piastrelle”. Non so perché ma più sono stupidi e più mi danno problemi (problemi stupidi ovviamente).

In generale è sempre meglio aprire un nuovo thread, comunque qui trovi la documentazione: http://www.cplusplus.com/reference/algorithm/next_permutation/


Rearranges the elements in the range [first,last) into the next lexicographically greater permutation.
[…]
The first such-sorted possible permutation (the one that would compare lexicographically smaller
to all other permutations) is the one which has all its elements sorted
in ascending order, and the largest has all its elements sorted in
descending order.
[…]
If the function can determine the next higher permutation, it rearranges the elements as such and returns true.
If that was not possible (because it is already at the largest possible
permutation), it rearranges the elements according to the first
permutation (sorted in ascending order) and returns false.

A me invece non è chiaro l’output 9 nel test-case di esempio. Se può procedere anche in obliquo non sono molti di più i possibili percorsi? precisamente 28.

Il testo del problema è sbagliato, sembrerebbe infatti che sia interessato invece solamente ai percorsi con mosse orizzontali e verticali, escludendo quelle oblique. In tal caso i 9 percorsi sono questi:
minato

Si si avevo fatto questa ipotesi e mi trovavo con 9 ma c’era una discordanza in quanto in un paragrafo precedente parlava di celle che condividono uno spigolo.
Comunque grazie per la tempestività.