Solitario2 80/100, wrong output ultimo case

Ciao ragazzi, vi scrivo per un aiutino, ho risolto solitario1 e posso dire di aver risolto anche solitario2, se non fosse per l’ultimo case dell’ultimo task, che mi da wrong output, facendomi così fare un 80/100.
Non ho idea di cosa possa essere andato storto, considerato che gli altri 53 case sono andati bene.
Mi sto perdendo qualcosa?

Il mio algoritmo è praticamente uguale a quello di solitario1 con un ulteriore ottimizzazzione, nulla di complicato.
Qualora fosse necessario il codice lo provvederò commentato!

Senza codice è difficile darti suggerimenti, puoi mandarlo?

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

int N, M;
int area;

void stampa_matrix(vector<vector<int>>& tris) {  // solamente per debugging
    for (int i = 0; i < tris.size(); i++) {
        for (int j = 0; j < tris[i].size(); j++) {
            cout << tris[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool is_safe(int x, int y, vector<vector<int>>& tris) {  // si accerta che mettendo una x, non avvenga nessun tris
    if (N - x - 1 >= 2) {
        if (tris[y][x + 1] && tris[y][x + 2]) {
            return false;
        }
        if (M - y - 1 >= 2) {
            if (tris[y + 1][x + 1] && tris[y + 2][x + 2]) {
                return false;
            }
            if (tris[y + 1][x] && tris[y + 2][x]) {
                return false;
            }
        }
    }
    if (y >= 2) {
        if (N - x - 1 >= 2) {
            if (tris[y - 1][x + 1] && tris[y - 2][x + 2]) {
                return false;
            }
        }
        if (x >= 2) {
            if (tris[y - 1][x - 1] && tris[y - 2][x - 2]) {
                return false;
            }
        }
        if (tris[y - 1][x] && tris[y - 2][x]) {
            return false;
        }
    }

    if (x >= 2) {
        if (tris[y][x - 1] && tris[y][x - 2]) {
            return false;
        }
        if (M - y - 1 >= 2) {
            if (tris[y + 1][x - 1] && tris[y + 2][x - 2]) {
                return false;
            }
            if (tris[y + 1][x] && tris[y + 2][x]) {
                return false;
            }
        }
    }

    if (M - y - 1 >= 2) {
        if (N - x - 1 >= 2) {
            if (tris[y + 1][x + 1] && tris[y + 2][x + 2]) {
                return false;
            }
            if (tris[y + 1][x - 1] && tris[y + 2][x - 2]) {
                return false;
            }
        }
        if (tris[y + 1][x] && tris[y + 2][x]) {
            return false;
        }
    }

    return true;
}

int gioca(int x, int y, vector<vector<int>>& tris, int curr, int max_found) {  // funzione recursiva
    if (x >= N) {                                                              // se è finita la riga
        return gioca(0, y + 1, tris, curr, max_found);
    }

    if (y >= M) {  // se sono finite le colonne, quindi si è visto tutto
        return curr;
    }

    int piazzate = (N * y) + x;
    if (ceil(((area - piazzate) * (float)2 / 3) + curr) < max_found) {  // ottimizzazione che ti fa fare 60 pt (avrei voluto scoprirlo prima)
        return -1;                                                      // per farla breve, se le x di questa soluzione + i 2/3 delle caselle libere < il totale che ho già trovato in un altra soluzione
    }                                                                   // non ha senso continuare
    //^ casi base

    // casi specifici
    int res = 0;

    bool safe = is_safe(x, y, tris);
    int tmp = tris[y][x];  // salvo il valore che aveva prima la casella
    if (safe) {
        tris[y][x] = 1;  // questo codice serve a provare tutte le combinazioni possibili

        res = gioca(x + 1, y, tris, curr + 1, max(res, max_found));  // funzione recursiva alla casella dopo, con una x trovata

        if (!tmp) tris[y][x] = 0;  // qua resetto a 0, solamente se il valore precedente era 0
    }

    return max(res, gioca(x + 1, y, tris, curr, max(res, max_found)));  // il massimo tra la giocata prima con la x ad 1 e questa con la x a 0
}

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

    int found = 0;
    vector<vector<int>> G(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int tmp;
            cin >> tmp;

            G[i][j] = tmp;
            if (tmp) {
                found++;  // con una variabile tengo conto delle x già presenti nell'input
            }
        }
    }

    area = N * M;  // mi serve per l'ottimizzazione

    int tmp = N;  // scambio le variabili per renderla compatibile con il codice scritto sopra
    N = M;
    M = tmp;

    int res = gioca(0, 0, G, 0, found);  //(x, y, &matrix, curr, max_found)
    cout << res - found << endl;         // al risultato tolgo quelle già trovate
}

ecco

La funzione is_safe non controlla che non ci sia un tris centrato in (y, x). Aggiungendo questo check prendi 100. Nota che questo non è invece un problema se nella griglia iniziale non ci sono X, quindi in solitario la soluzione è corretta (e in solitario2 prende i subtask 2-4 per sbaglio…).

Un altro modo “accidentale” per fixare il bug è fare la seconda chiamata ricorsiva (gioca(x + 1, y, tris, curr, max(res, max_found))) solo se tris[y][x] == 1, e altrimenti ritornare semplicemente res. Perché questo risolve? (Non è così ovvio.)

1 Mi Piace

Ciao!
Grazie mille, sei un salvatore, non so da quanto mi scervellavo qua per poi scoprire che la funzione is_safe era tarocca :/
Implementando il controllo ora funziona tutto, in oltre hai fatto un’acuta osservazione consigliandomi l’altro modo “accidentale”, ma penso intendessi di chiamarla solo se tris[y][x] == 0.
L’ho implementato così:

    int res = 0;

    bool safe = is_safe(x, y, tris);
    int tmp = tris[y][x]; 
    if (safe) {
        tris[y][x] = 1;
        res = gioca(x + 1, y, tris, curr + 1, max(res, max_found));
        if (!tmp) tris[y][x] = 0;                                 
    }

    if (tmp) {
        return max(res, max_found);
    } else {
        return max(res, gioca(x + 1, y, tris, curr, max(res, max_found))); 
    }

Dal momento che quello che fa il codice è provare tutte le combinazioni mettendo 1 oppure 0, se il valore prima era 1, e quindi non viene poi resettato a 0, è inutile quindi, come dicevi, fare la giocata che sarebbe dovuta essere con 0, poichè sarebbe la stessa cosa di prima.

Grazie mille :D

Sì scusa, era 0… :sweat_smile: