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.
