Domino massimale 0/100

Aiuto
1

Buongiorno,
sto cercando di risolvere il problema Domino massimale.
Purtroppo faccio 0/100. Ho qualche difficoltà a capire quale strategia utilizzare per risolvere il problema.
Al momento non utilizzo la ricorsione, anche se ne viene suggerito l’uso.

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MAXN 10
using namespace std;

struct tessera{
    int a;
    int b;
    int w;
};

static int N;
//static int sx[MAXN], dx[MAXN];

void stampa_tessere(vector <tessera> t){
    cout << "Stato tessere ("<<t.size()<<")"<<endl;
    for (int i=0; i<t.size(); i++)
        cout << "("<<t[i].a<<","<<t[i].b<<")"<<" "<<t[i].w<<endl;
}

static FILE *fin, *fout;

int main(){
    int val, val1, totale = 0;
    std::vector <tessera> t;
    fin = fopen("input.txt", "r");
    //fout = fopen("output.txt", "w");
    assert(1 == fscanf(fin, "%d", &N));
    for(int i=0; i<N; i++) {
        //assert(2 == fscanf(fin, "%d%d", sx+i, dx+i));
        //cout<<"sx "<<sx[i]<<" dx "<<dx[i]<<endl;        
        assert(2 == fscanf(fin, "%d%d", &val, &val1));
        tessera tess;
        tess.a = val;
        tess.b = val1;
        tess.w = 1;
        t.push_back(tess);
    }

    bool update = true;
    int it = 0;
    while (update){
        cout << "Iterazione "<<it<<endl;
        stampa_tessere(t);
        update = false;
        for (int i=0; i<t.size()-1; i++){
            for (int j=i+1; j<t.size()-1; j++){
                if (t[i].a == t[j].a){
                    t[i].a = t[j].b;
                    t[i].w++;
                    if (t[i].w > totale)
                        totale = t[i].w;
                    update = true;
                    t.erase(t.begin()+j);
                    break;
                }

                if (t[i].a == t[j].b){
                    t[i].a = t[j].a;
                    t[i].w++;
                    if (t[i].w > totale)
                        totale = t[i].w;                    
                    update = true;
                    t.erase(t.begin()+j);
                    break;
                }

                if (t[i].b == t[j].a){
                    t[i].b = t[j].b;
                    t[i].w++;
                    if (t[i].w > totale)
                        totale = t[i].w;                    
                    update = true;
                    t.erase(t.begin()+j);
                    break;
                }

                if (t[i].b == t[j].b){
                    t[i].b = t[j].a;
                    t[i].w++;
                    update = true;
                    if (t[i].w > totale)
                        totale = t[i].w;                    
                    t.erase(t.begin()+j);
                    break;
                }
            }
        }
        it++;
    }

    cout <<"Totale "<<totale<<endl;
    fclose(fin);
    //fclose(fout);
    return 0;
}

Non riesco a capire quale sia la strategia migliore per capire se concatenare oppure no due tessere. Io erroneamente concateno le prime tessere che trovo e quindi non riesco ad ottenere la soluzione corretta. Qualcuno riesce ad aiutarmi?

2

Non mi sembra che ci sia una strategia per decidere se concatenare o no due tessere, c’è da provarle tutte e trovare la sequenza più lunga. (Ricorsione)

3

Ok, grazie!

Quindi partendo da una tessera a caso provo a concatenarla con tutte le altre e ogni volta che si concatena aggiorno il totale delle tessere concatenate?

Come faccio a capire quando non posso più concatenare? Guardo se non ci sono state concatenazioni nella precedente iterazione?

C’è una strategia per concatenare tessere uguali? Ad esempio nei dati di input (1,0) e (0,1) conviene trasformarla in (1,1) o (0,0)?

4

Si.

Direi quando o le ho messe tutte o nessuna delle tessere che ho ancora in mano ha numeri identici ai due ( o uno) sul tavolo.

Direi di lasciar perdere le strategie.
Inoltre c’è un altro post sull’argomento, può essere utile dargli un’occhiata.

5

Sono riuscito a raggiungere 68.42/100. Mi mancano però i subtask 09-13 e 17.
Non capisco però così manchi al mio codice. Qualcuno riesce ad aiutarmi?

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
using namespace std;

struct tessera{
    int a;
    int b;
};
void combina(vector <tessera> &t, vector <bool> &used, int index, int &totale, int &max_value){
    bool update = true;
    while (update){
        update = false;
        for (int i=0; i<t.size(); i++){
            if (i!=index && !used[i]){
                if (t[i].a == t[index].a){
                    used[i] = true;
                    totale++;
                    t[index].a = t[i].b;
                    update = true;
                }
                else {
                    if (t[i].a == t[index].b){
                        used[i] = true;
                        totale++;
                        t[index].b = t[i].b;
                        update = true;

                    }
                    else{
                        if (t[i].b == t[index].a){
                            used[i] = true;
                            totale++;
                            t[index].a = t[i].a;
                            update = true;
                        }
                        else{
                            if (t[i].b == t[index].b){
                                used[i] = true;
                                totale++;
                                t[index].b = t[i].a;
                                update = true;
                            }
                        }
                    }
                }
            }
        }
    }
    if (totale > max_value){
        max_value = totale;
    }
}

int main(){
    int val, val1, totale = 0;
    int max_value = 0;
    std::vector <tessera> t;
    fin = fopen("input.txt", "r");
    fout = fopen("output.txt", "w");
    assert(1 == fscanf(fin, "%d", &N));
    std::vector<bool> used;
    for(int i=0; i<N; i++) {
        assert(2 == fscanf(fin, "%d%d", &val, &val1));
        tessera tess;
        tess.a = val;
        tess.b = val1;
        t.push_back(tess);
        used.push_back(false);
    }
    for (int i=0; i<t.size(); i++){
        totale = 1;
        combina(t,used, i,totale, max_value);
        cout << "totale "<<totale<<endl;
       
       //cleaning combinations
        for (int j=0; j<t.size(); j++)
            used[j] = false;
    }

    cout <<"Totale finale "<<max_value<<endl;
    return 0;
}
6

Avevo proposto:

e non mi sembra che questa tua ultima soluzione vada secondo il consiglio perchè mi pare che per ogni prima tessera il tuo codice provi una sola sequenza e non è detto che questa sia la migliore.
Voglio dire che se a un certo punto nella combina() è possibile inserire tre tessere diverse bisogna provarle tutte tre!

Esempio se a tavola c’è una tessera 4-2 ed in mano hai 2 5 e 2-2 se metti prima la 2-5 in tutto ne combini due ma se metti prima l’altra le metti tutte e tre.

7

Mi è chiara la logica per risolvere il task, ho però qualche problema a livello di codice ad implementare la soluzione ricorsiva.
Oltre al fatto, che mi restituisce segmentation fault, non sono certo che il passaggio dei parametri sia corretto: passaggio per valore o per riferimento?
La funzione test mi controlla se le tessere si possono combinare e le combina.

bool test(vector <tessera> &t, int index, int i, vector <bool> used, int &totale){
    if (i!=index && !used[i]){
        if (t[i].a == t[index].a){
            used[i] = true;
            totale++;
            t[index].a = t[i].b;
            return true;
        }
        else {
            if (t[i].a == t[index].b){
                used[i] = true;
                totale++;
                t[index].b = t[i].b;
                return true;
            }
            else{
                if (t[i].b == t[index].a){
                    used[i] = true;
                    totale++;
                    t[index].a = t[i].a;
                    return true;
                }
                else{
                    if (t[i].b == t[index].b){
                        used[i] = true;
                        totale++;
                        t[index].b = t[i].a;
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

La funzione ricorsiva combina2 invece prova tutte le permutazioni

void combina2(vector <tessera> t, int idx, int idx2, vector <bool> &used, int volte, int &totale){
    if (volte != 0){
        for (int j=0; j<t.size();j++){
            combina2(t,idx,j, used, volte--, totale);
            if (test(t,idx,j,used))
                totale++;
            if (totale > max_value)
                max_value = totale;
            for (int r=0; r<used.size(); r++)
                used[r] = false;
        }
    }
}

Estratto del main dove chiamo la funzione combina2 per trovare il percorso più lungo:

    for (int i=0; i<t.size(); i++){
        //starting card
        totale = 1;
        combina2(t,i,0,used,t.size()-1,totale);
       //cleaning combinations
        for (int j=0; j<t.size(); j++)
            used[j] = false;
    }

Qualcuno riuscirebbe ad aiutarmi?

8

Per debuggare cose come segmentation fault ti consiglio di usare valgrind oppure di compilare con queste flag.

1 Mi Piace