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!
#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
}
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.)
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.
Mi sono permesso di prendere il tuo codice e fare quella modifica ad is_safe, e anche con questo tipo di modifica il codice fa 100/100.
Il fatto è che, in attesa di implementare una soluzione da capo, mi sono messo a guardare il codice, ed effettivamente togliendo quella condizione “ultimo caso base” il codice fa 50/100.
Non saprei spiegarmi come tu abbia dimostrato quell’ottimizzazione, onestamente ci ho riflettuto un po’ ma da un lato ho una mezza idea del perché una cosa simile possa funzionare, ma dall’altro lato non riesco a spiegarmi perché proprio 2/3… se te lo ricordi ancora potresti spiegarmi come mai funziona?
“Se in passato ho già trovato una soluzione che mette più X rispetto a quante ne abbia messe io finora sommate a quante ne abbia visitate io finora, allora non ha senso continuare”
Ma non capisco perché sommare a curr quelle già visitate invece che quelle da visitare…
se ti stai riferendo a questa riga il “area-piazzate” è il numero di caselle rimaste da controllare, quindi curr+ (area-piazzate)*2/3 è il massimo di “x” che potrò raggiungere (numero di “x” messe più il massimo numero di “x” che potrò mettere nello spazio che manca). Quindi la condizione è: se anche mettendo tutte le x possibili non supero il massimo che ho trovato, non ha senso continuare
