Quasi Palindromi con funzione ricorsiva

Aiuto
1

Buon giorno a tutti, sto provando a risolvere l’esercitazione Quasi palindromi, cercando al tempo stesso d’esercitarmi con la ricorsione e le permutazioni (mi rendo conto che no è ottimale ma lo considero un allenamento da sistemare in seguito). Ho notato un’anomalia nell’esecuzione che con capisco sia un mio problema o del compilatore online (sicuramente sarà colpa mia).
Utilizzando il portale allenamento ottengo 88.89/100 con errore al test cast 005 (stringhe non palindrome) mentre con il correttore online mi funziona solamente al test 1 mentre gli altri test mi dice che sono errati ma confrontandoli non noto alcuna differenza, esempio;
File Input
3 8
01170005
00170000
00650046

Output Atteso
01170005
00650046
00170000

Output Prodotto
00170000
00650046
01170005

mi da errore (anche se l’output non sono identici comunque soddisfa le condizioni richieste), ecco il codice:

    #include < iostream >
    #include < fstream >
    #include < vector >
    #include < set >
    using namespace std;
    typedef vector<string> pp;
    void scambia(pp &x,int i,int j);
    void permuta(pp &x,int i ,int M, set<pp> &db);
    bool quasipalindrome(pp &x, int riga, int colonna ,int M);
    int main(){
        ifstream in("input.txt",ios::in);
        ofstream out("output.txt",ios::out);

        int i,j,N,M;
        pp rettangolo;
        set<pp> permutazioni;
        string temp;
        in>>M>>N;
        for(i=0;i<M;i++){
            in>>temp;
            rettangolo.push_back(temp);
        }
        permuta(rettangolo,0,M,permutazioni);
        set<pp>::iterator it = permutazioni.begin();
        bool trovato=false;
        int conta;
        while(it!=permutazioni.end()&&trovato==false){
            conta=0;
            for(j=0;j<N;j++){
                pp p=(*it);
                if(quasipalindrome(p,0,j,M)==true){
                    conta++;
                }
            }
            if(conta==N){
                trovato=true;
                for(i=0;i<M;i++){
                    out<<(*it)[i]<<endl;
                }
            }
            it++;
        }
    }
    void permuta(pp &x,int i ,int M, set<pp> &db){
        int j;
    	if(i==M){
            db.insert(x);
        }else{
            for( j=i ; j<M ; j++ ){
                scambia(x,i,j);
                permuta(x,i+1,M,db);
                scambia(x,i,j);
    		}
    	}
    }

    void scambia(pp&x,int i,int j){
    	string temp;
    	temp = x[i];
    	x[i] = x[j];
    	x[j] = temp;
    }
    bool quasipalindrome(pp &x, int riga, int colonna ,int M){
        string a = x[riga];
        string b = x[M-1-riga];

        if(riga>(M-1-riga)/2)
            return true;
        if (a[colonna]!=b[colonna] && a[colonna]!='0' && b[colonna]!='0'){
            return false;
        }else{
            return true && quasipalindrome(x,riga+1,colonna,M);
        }
    }
2

Ciao! Sinceramente è la prima volta che sento parlare del correttore online :sweat_smile:
Credo che il problema sia dovuto alla mancanza di un programma che verifichi la validità della tua soluzione, sembra che controlli solo che il tuo output sia uguale a quello che ha salvato, se è diverso lo considera sbagliato.
Passando al codice :new_moon_with_face: l’errore è minuscolo: hai messo (M-1-riga)/2 anzichè (M-1-riga) in quasipalindrome. Inoltre, sebbene capisco ti stia esercitando sulle ricorsive, forse potrebbe interessarti conoscere swap e next_permutation (dato che ti semplifichrebbero il lavoro).

1 Mi Piace
3

Grazie per la risposta, l’errore era banale :man_facepalming:, per quanto riguarda swap e next_permutation … l’esercitazione è stata svolta volutamente senza :wink:.
Per quanto riguarda il correttore, nonostante in piattaforma ora riesco ad ottenere 100/100, con il correttore online, link disponibile sul sito delle olimpiadi (basta che clicchi Allenamenti e lo trovi sotto il portale degli allenamenti),supero soltanto il primo test … sembra non preveda la possibilità chi ci siano più soluzioni corrette!
Grazie ancora

1 Mi Piace