Caccia agli interruttori

Aiuto
1

Buongiorno, avrei bisogno di aiuto per il problema interruttori di Algobadge. Il codice da risultati sbagliati (1 corretto su 24) e alcuni output non vengono prodotti.
Grazie in anticipo.
Il mio codice:

#include <iostream>
#include <fstream>
#include <utility>
#include <vector>

using namespace std;

vector<vector<bool>> connectMatrix;
vector<int> nodeWeight;

void controllaVicini(int startNode, int N) {
    
    for (int vicino = 0; vicino < N; vicino++) {
        
        if (!connectMatrix[startNode][vicino]);
        else if (nodeWeight[vicino] == 0 || nodeWeight[startNode] + 1 < nodeWeight[vicino]) {
            nodeWeight[vicino] = nodeWeight[startNode] + 1;
            controllaVicini(vicino, N);
        }
    }
}

void solve(int t) {
    int N, A, B;
    cin >> N >> A >> B;

    vector<int> Z(A), X(B), Y(B);
    
    for (int i = 0; i < A; i++) {
        cin >> Z[i];
    }

    for (int i = 0; i < B; i++) {
        cin >> X[i] >> Y[i];
    }

    // start

    // riempimento della matrice di adiacenza
    for (int i = 0; i < N; i++) {
        vector<bool> mBuffer;
        for (int i = 0; i < N; i++) {
            mBuffer.push_back(false);
        }
        connectMatrix.push_back(mBuffer);
    }

    for (int i = 0; i < B; i++) {
        connectMatrix[X[i]][Y[i]] = true;
        connectMatrix[Y[i]][X[i]] = true;
    }

    // riempimento nodeWeight
    for (int i = 0; i < N; i++) {
        nodeWeight.push_back(0);
    }

    for (int i = 0; i < A; i++) {
        nodeWeight[Z[i]] = 1;
    }

    // ogni lampadina di tipo 1 controlla vicini
    for (int i = 0; i < A; i++) {
        controllaVicini(Z[i], N);
    }

    // trova num e idx
    int idx; // memorizza qui l'indice della lampadina
    int num = 0; // memorizza qui il numero di interruttori

    for (int i = 0; i < N; i++) {

        if (nodeWeight[i] > num) {
            
            num = nodeWeight[i];
            idx = i;
        }
    }

    // end

    cout << "Case #" << t << ": " << idx << " " << num << "\n";
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}
2

Ciao! Stai inizializzando connectMatrix e nodeWeight come variabili globali, quindi non si azzerano ogni volta che chiami solve come fanno ad esempio Z, X e Y.
Questo vuol dire che quando riempi connectMatrix e nodeWeight all’interno della funzione solve usando push_back, stai aggiungendo in fondo a quello che è rimasto dai precedenti test.
Per fare un esempio: in questo caso connectMatrix[0][1] rappresenterĂ  sempre la presenza o meno di un arco tra i nodi 0 e 1 del primo test e non del test attuale.
Per risolvere questo problema puoi semplicemente dichiarare entrambe le variabili all’interno di solve così che vengano eliminate alla fine di ogni funzione per poi essere inizializzate nuovamente da zero alla prossima chiamata. Per accedere a queste variabili all’interno della funzione controllaVicini puoi passarle come argomento ogni volta (passandole come riferimento eviti di crearne una copia ad ogni chiamata che può diventare molto lavoro inutile e allo stesso tempo riesci a modificare nodeWeight da dentro la funzione).
Questo dovrebbe risolvere il problema degli output errati ma il tuo codice potrebbe avere anche problemi legati alla ricorsione o alla velocità (Ad esempio in controllaVicini per ogni nodo che stai visitando iteri su tutti gli altri nodi per controllare se sono adiacenti a quello attuale mentre, usando una lista di adiacenza anziché una matrice di adiacenza, basterebbe iterare sui nodi adiacenti a quello che stai attualmente visitando).

1 Mi Piace
3

Grazie! Ho capito il mio errore. Ho provato a usare una lista di adiacenza e l’ho dichiarata dentro solve(), nodeWeight invece non sapevo come aggiungerla tra i parametri di controllaVicini() perchè non sono sicuro se modificando i suoi valori all’interno della funzione li modifica anche fuori da essa, perciò l’ho comunque dichiarata come variabile globale e l’ho riempita con zeri all’inizio di ogni test. Provando il codice funziona (ha prodotto l’output a 9 casi ed erano tutti corretti) ma probabilmente è ancora troppo lento (erano 9 casi su 24).
Per caso avete qualche consiglio?
Il mio codice:

#include <iostream>
#include <fstream>
#include <utility>
#include <vector>

using namespace std;

vector<int> nodeWeight;

void controllaVicini(int node, vector<vector<int>> list) {

    for (int i = 0; i < list[node].size(); i++) {

        int endNode = list[node][i];
        if (nodeWeight[endNode] == 0 || nodeWeight[node] + 1 < nodeWeight[endNode]) {

            nodeWeight[endNode] = nodeWeight[node] + 1;
            controllaVicini(endNode, list);
        }
    }
}

void solve(int t) {
    int N, A, B;
    cin >> N >> A >> B;

    vector<int> Z(A), X(B), Y(B);
    
    for (int i = 0; i < A; i++) {
        cin >> Z[i];
    }

    for (int i = 0; i < B; i++) {
        cin >> X[i] >> Y[i];
    }

    // aggiungi codice...

    vector<vector<int>> connectList(N);
    nodeWeight.resize(N);

    // inizializzare connectList
    for (int i = 0; i < B; i++) {

        connectList[X[i]].push_back(Y[i]);
        connectList[Y[i]].push_back(X[i]);
    }

    // inizializzare nodeWeight (interruttori di tipo 1 hanno valore iniziali 1)
    for (int i = 0; i < N; i++)
        nodeWeight[i] = 0;
    for (int i = 0; i < A; i++)
        nodeWeight[Z[i]] = 1;
    
    // controllo di tutti i nodi a partire dagli interruttori di tipo 1
    for (int i = 0; i < A; i++) 
        controllaVicini(Z[i], connectList);

    // trovare idx e num
    int idx; // memorizza qui l'indice della lampadina
    int num = 0; // memorizza qui il numero di interruttori

    for (int i = 0; i < N; i++) {

        if (nodeWeight[i] > num) {

            num = nodeWeight[i];
            idx = i;
        }
    }

    // end

    cout << "Case #" << t << ": " << idx << " " << num << "\n";
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}
4

Per passare nodeWeight come parametro a controllaVicini in modo che venga comunque modificato all’interno della funzione puoi passarlo per riferimento e non per valore (che è quello che succede di default), ma anche la tua soluzione non dovrebbe dare problemi su nodeWeight.
Per quanto riguarda la lentezza, passare list per riferimento dovrebbe bastare per velocizzare il codice a sufficienza.

Cosa vuol dire passare per riferimento?

Passare una variabile per riferimento anziché per valore (che è quello che stai facendo tu in questo momento) fa sì che la funzione “lavori” direttamente sulla variabile che tu passi come parametro e non ne crei una copia da utilizzare all’interno della funzione come farebbe altrimenti.
Questo non solo permette di modificare una variabile all’interno di una funzione ma evita anche di creare ogni volta una copia del parametro che, in casi dove ci sono vettori abbastanza grandi, può aumentare significativamente la complessità.
Per passare un parametro per riferimento basta aggiungere & prima del nome del parametro nella dichiarazione della funzione così:

void controllaVicini(int node, vector<vector<int>> &list)

Riassumendo: puoi passare per riferimento nodeWeight come parametro a controllaVicini per modificarlo all’interno della funzione e, soprattutto, passando list per riferimento eviti di crearne una copia ad ogni chiamata di controllaVicini velocizzando significativamente il tuo codice.