Aiuto per solitario2

Aiuto
1

Ho scritto questo codice per risolvere solitario2 ma non capisco perché l’output del codice supera sempre quello giusto di uno o di due. Ho creato una matrice con 2 zeri in più per lato per evitare problemi quando controllo se la x si può aggiungere.

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

int avanti(int N, int M, vector<vector<int>> G, int c, int r){
    int opz1,opz2;
    opz1=0;
    if(c==M+1 && r==N+1){
        return 0;
    }
    if(c!=M+1){
        opz1=avanti(N,M,G,c+1,r);
    }
    else{
        opz1=avanti(N,M,G,2,r+1);
    }
    opz2=0;
    // i controlli dovrebbero stare bene
    if(!(G[r-1][c+1]==1 && G[r+1][c-1]==1)&&!(G[r-1][c-1]==1 && G[r+1][c+1]==1)&&!(G[r-1][c]==1 && G[r+1][c]==1)&&!(G[r][c-1]==1 && G[r][c+1]==1)&&!(G[r-1][c]==1 && G[r-2][c]==1)&&!(G[r+1][c]==1 && G[r+2][c]==1)&&!(G[r][c-1]==1 && G[r][c-2]==1)&&!(G[r][c+1]==1 && G[r][c+2]==1)&&!(G[r-1][c-1]==1 && G[r-2][c-2]==1)&&!(G[r+1][c-1]==1 && G[r+2][c-2]==1)&&!(G[r-1][c+1]==1 && G[r-2][c+2]==1)&&!(G[r+1][c+1]==1 && G[r+2][c+2]==1))
    {
        G[r][c]=1;
        /*
        cout<<endl;
        for(int a=0;a<N+4;a++){
            for(int b=0;b<M+4;b++){
                cout<<G[a][b]<<" ";
            }
            cout<<endl;
        }*/
        
        if(c!=M+1){
        opz2=avanti(N,M,G,c+1,r)+1;
        }
        else{
        opz2=avanti(N,M,G,2,r+1)+1;
        }
    }
    return max (opz1,opz2);


}


int gioca(int N, int M, vector<vector<int>> G)
{
    vector<vector<int>> V(N+4,vector<int> (M+4));
    for(int r=2;r<N+2;r++){
        for(int c=2;c<M+2;c++){
            V[r][c]=G[r-2][c-2];
        }
    }/*
    cout<<endl;
    for(int r=0;r<N+4;r++){
        for(int c=0;c<M+4;c++){
            cout<<V[r][c]<<" ";
        }
        cout<<endl;
    }
    */
    return avanti(N,M,V,2,2);
}


int main()
{
    int N, M;
    cin >> N >> M;
    assert(cin.good());

    vector<vector<int>> G(N, vector<int>(M));
    for(auto& x : G)
        for(auto& y : x)
            cin >> y;
    assert(cin.good());

    cout << gioca(N, M, G) << endl;
}
2

Ciao, a me sembra che il ragionamento dietro il codice sia corretto. Non sono stato a guardare molto nel dettaglio l’enorme fila di controlli per le caselle adiacenti, però sostituendoli con i miei controlli faccio un paio di testcase in più (per esempio il 3 e altri che con il tuo codice falliscono). Siccome poi dovrai comunque implementare di nuovo buona parte del programma, ti do qualche suggerimento per migliorare il tuo approccio e al tempo stesso ottimizzare per non andare in contro limiti di tempo:

  • Non è un task con grader, quindi non c’è bisogno di mantenere il main originale: inizializzi il vettore G da cui poi copi i valori nella funzione gioca…

  • I limiti dei testcase sono estremamente piccoli! Con N \times M \leq 42 e 1 \leq N, M \leq 10, puoi anche pensare di inizializzare un array statico della dimensione massima e poi riempirlo quanto basta ogni volta

  • Al posto di creare un’enorme condizione all’interno dell’if, crea una funzione che controlla passo passo tutte le possibili combinazioni: è più pulito e se la dichiari come inline bool non hai neanche un drastico calo di performance

  • Come argomenti della funzione avanti, perché non salvarti il massimo di X che hai messo, nonché il più grande valore che il massimo ha avuto?

  • Estensione del punto precedente: esiste una condizione che ti fa capire quando il numero di X messe non potrà superare il massimo numero mai raggiunto?

Spero di essere stato d’aiuto, scusa per la risposta in ritardo!

1 Mi Piace
3

Grazie mille, creando come hai detto la funzione per controllare mi sono accorto che il problema era che il programma non metteva x nell’ultima casella e che se arrivava su una casella dove la x c’era già aumentava comunque di uno il numero di x. Adesso vedo di ottimizzarlo per il tempo

4

Di niente, se ti serve una mano con l’ottimizzazione chiedi pure :slight_smile: