Ho scritto una soluzione per solitario 2 e la logica mi sembra anche corretta, ma non passa nessun test case apparte il 2 (=_=). Questo è il codice:
#include <iostream>
#include <vector>
#include <cassert>
#include <list>
#define pb push_back
using namespace std;
int sol=0;
bool verifica(vector<vector<int>> G, int i, int j){
// +
if(G[i-1][j]==1 and G[i-2][j]==1) return false;
if(G[i][j-1]==1 and G[i][j-2]==1) return false;
if(G[i+1][j]==1 and G[i+2][j]==1) return false;
if(G[i][j+1]==1 and G[i][j+2]==1) return false;
// x
if(G[i-1][j-1]==1 and G[i-2][j-2]==1) return false;
if(G[i+1][j-1]==1 and G[i+2][j-2]==1) return false;
if(G[i-1][j+1]==1 and G[i-2][j+2]==1) return false;
if(G[i+1][j+1]==1 and G[i+2][j+2]==1) return false;
// + e x con casella centrale
if(G[i-1][j]==1 and G[i+1][j]==1) return false;
if(G[i][j+1]==1 and G[i][j-1]==1) return false;
if(G[i-1][j+1]==1 and G[i+1][j-1]==1) return false;
if(G[i-1][j-1]==1 and G[i+1][j+1]==1) return false;
return true;
}
void gioca(int ix, int jx, int N, int M, vector<vector<int>> G){
int k=0;
for(int i=ix; i<N; i++){
for(int j=jx; j<M; j++){
if(G[i+2][j+2]==0 and verifica(G,i+2,j+2)){
k++;
gioca(i,j+1,N,M,G);
G[i+2][j+2]=1;
}
}
}
sol = max(sol,k);
/*
cout << "DEBUG: " << sol << endl;
for(int i = 0; i<N; i++){
for(int j=0; j<M; j++) cout << G[i+2][j+2];
cout << endl;
}*/
}
int main()
{
int N, M;
cin >> N >> M;
assert(cin.good());
vector<vector<int>> G(N+4, vector<int>(M+4,2));
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> G[i+2][j+2];
}
}
assert(cin.good());
gioca(0, 0, N, M, G);
cout << sol << endl;
}
Aggiungo alla griglia una “cornice” di larghezza 2 di “2” (spero mi sia spiegato bene ) per non avere problemi quando controllo le caselle dei bordi. Semplicemente la funziona “gioca” controlla se è possibile aggiungere una “X” in una casella (i,j) iterando nella “matrice” in avanti da una casella iniziale (ix,jx), se si può aggiungere una “X” si richiama la funzione passando come casella iniziale da cui iterare quella successiva a dove si poteva mettere la “X” (N.B. non inserendo la x). Dopo la ricorsione si inserisce la “X” e si continua ad iterare. Alla fine la variabile globale sol assume il massimo valore tra sol e le x inserite. Scusate la spiegazione lunga ma volevo rendervi tutto chiaro , btw dov’è l’errore?
Ottima idea quella di mettere una cornice alla matrice, in modo da non sforarla, mi era venuto in mente anche a me ma per pigrizia l’ho risolta in java mettendo letteralmente un try catch per ogni confronto LOL
Ancora meglio sarebbe mettere un bound agli indici in verifica, così non avresti bisogno della matrice, doverla inizializzare ad un valore invalido e ricordarsi di essa nei controlli.
Detto questo ti consiglio di rivedere il tuo passo induttivo nelle chiamate ricorsive.
Di solito si compone:
in primis il caso base
l’esecuzione ricorsiva alla ricerca “dell’ottimo”
il ritorno allo stack delle chiamate precedenti.
Tralasciando possibili casi base per velocizzare l’algo, pensando a come normalmente si scorre una matrice, ad ogni chiamata devo sapere la riga e la colonna in cui mi trovo, se la colonna è l’ultima, la prossima chiamata ricorsiva la farò partendo dalla colonna zero nella prossima riga.
Se invece mi trovo sia all’ultima riga che all’ultima colonna restituisco “l’ottimo” fin ora trovato (che quindi mi devo “portare dietro”).
Per quanto riguarda invece il core del problema, poniti queste domande:
Grazie per la risposta :). Comunque tecnicamente per come sono strutturati i cicli for con le condizioni i<N e j<M la matrice dovrebbe scorrere bene. Poi l’ottimo lo tengo salvato sempre nella variabile globale sol :(.
Io queste domande me le sono fatte, è penso anche di avere implementato le risposte
if(G[i+2][j+2]==0 and verifica(G,i+2,j+2))
G[i+2][j+2]=1; e k++;
gioca(i,j+1,N,M,G);
sol = max(sol,k); che tiene in sol sempre il numero maggiore di x
Solo per sicurezza ti consiglio di assicurarti innanzitutto che verifica sia giusta e non sfori la cornice.
G[i+2][j+2]==0 // puoi metterlo come case di verifica
Non tanto per efficienza, ma per leggibilità del codice, ti consiglio di definire globalmente N,M,G.
Le tue soluzioni alle domande sono giuste, ma localmente alla chiamata.
Oltre a portarti dietro il numero di riga e colonna, dovresti portarti dietro quante x hai messo nel ramo ricorsivo in cui ti trovi, e il numero massimo globale di x che sei riuscito a mettere fino a quel momento.
Con
G[i+2][j+2]=1;
È come se “macchiassi” la cella, il che ti serve per ricordarti nel tuo ramo ricorsivo che li hai messo una x, ma quando anche la chiamata nella quale hai messo la x deve, ritornare, devi ricordarti di pulire la cella, altrimenti le altre chiamate di altre ricorsioni la vedranno già “macchiata”
#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#define pb push_back
using namespace std;
int sol=0;
int N,M;
bool verifica(vector<vector<int>> G, int i, int j){
// la casella è vuota?
if(G[i][j]!=0) return false;
// +
if(G[i-1][j]==1 and G[i-2][j]==1) return false;
if(G[i][j-1]==1 and G[i][j-2]==1) return false;
if(G[i+1][j]==1 and G[i+2][j]==1) return false;
if(G[i][j+1]==1 and G[i][j+2]==1) return false;
// x
if(G[i-1][j-1]==1 and G[i-2][j-2]==1) return false;
if(G[i+1][j-1]==1 and G[i+2][j-2]==1) return false;
if(G[i-1][j+1]==1 and G[i-2][j+2]==1) return false;
if(G[i+1][j+1]==1 and G[i+2][j+2]==1) return false;
// + e x con casella centrale
if(G[i-1][j]==1 and G[i+1][j]==1) return false;
if(G[i][j+1]==1 and G[i][j-1]==1) return false;
if(G[i-1][j+1]==1 and G[i+1][j-1]==1) return false;
if(G[i-1][j-1]==1 and G[i+1][j+1]==1) return false;
return true;
}
void gioca(int ix, int jx, vector<vector<int>> G, int k){
for(int i=ix; i<N+2; i++){
for(int j=jx; j<M+2; j++){
if(verifica(G,i,j)){
gioca(i,j+1,G,k);
G[i][j]=1;
k++;
}
}
jx=0;
}
sol = max(sol,k);
}
int main()
{
cin >> N >> M;
assert(cin.good());
vector<vector<int>> G(N+4, vector<int>(M+4,2));
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> G[i+2][j+2];
}
}
assert(cin.good());
gioca(2, 2, G, 0);
cout << sol << endl;
}
Ho reso N ed M globali e ho trovato l’errore, ossia mancava questo jx=0; non facendo continuare bene l’iterazione della matrice.
Ora il codice mi fa 50/100 e non penso ci siano errori di implementazione, il problema è che va in TLE nella 5°,6° e 7° sub task (6° e 7° ne fa solo 2 ciascuno, 5° zero). Idee per ottimizzare?
Comunque stavo cercando di darti consigli sulla base di come avevo impostato io il codice, ma non avevo pensato al fatto che se passi G per copia, le cose cambiano un pó.
Mea culpa.
Rimanendo sulla tua soluzione, per cercare di ottimizzare, pensa a che punti della ricorsione puoi fermarti prima del caso base e quindi tagliare il ramo ricorsivo in anticipo.
Un piccolo spunto è…
dalla posizione della matrice in cui ti trovi, quante x al massimo/meglio potrai mettere? (ricordandosi che non ce ne possono essere 3 consecutive).
In totale, tra quelle che hai già aggiunto e quelle che potresti mettere, trovi un nuovo ottimo?
Con la risposta all ultima domanda sai se continuare o fermarti prima.
Alla fine ho ottenuto 100/100 con questo codice. Forse ho un attimino barato con lo stratagemma in “gioca” che lavora sulle subtask specifiche, ma senza non passavano alcuni test case per TLE e un altro per output not correct . Non so quanto sia lecito sinceramente, ma non ci lamentiamo dell 100/100
#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <math.h>
#define pb push_back
#pragma GCC optimize("03")
using namespace std;
int sol=0;
int N,M;
int a,b,c;
bool verifica(vector<vector<int>> G, int i, int j){
// la casella è vuota?
if(G[i][j]!=0) return false;
// +
if(G[i-1][j]==1 and G[i-2][j]==1) return false;
if(G[i][j-1]==1 and G[i][j-2]==1) return false;
if(G[i+1][j]==1 and G[i+2][j]==1) return false;
if(G[i][j+1]==1 and G[i][j+2]==1) return false;
// x
if(G[i-1][j-1]==1 and G[i-2][j-2]==1) return false;
if(G[i+1][j-1]==1 and G[i+2][j-2]==1) return false;
if(G[i-1][j+1]==1 and G[i-2][j+2]==1) return false;
if(G[i+1][j+1]==1 and G[i+2][j+2]==1) return false;
// + e x con casella centrale
if(G[i-1][j]==1 and G[i+1][j]==1) return false;
if(G[i][j+1]==1 and G[i][j-1]==1) return false;
if(G[i-1][j+1]==1 and G[i+1][j-1]==1) return false;
if(G[i-1][j-1]==1 and G[i+1][j+1]==1) return false;
return true;
}
void gioca(int ix, int jx, vector<vector<int>> G, int k){
b = N+1-ix;
c = M+2-jx;
// Piccolo stratagemma per far passare tutti i test case :'(
if(N*M>36) if(sol>=ceil((M*b+c)*2.0/3)+k-1) return;
if(N*M<=36) if(sol>=ceil((M*b+c)*2.0/3)+k) return;
for(int i=ix; i<N+2; i++){
for(int j=jx; j<M+2; j++){
if(verifica(G,i,j)){
gioca(i,j+1,G,k);
G[i][j]=1;
k++;
}
}
jx=0;
}
sol = max(sol,k);
}
int main()
{
cin >> N >> M;
assert(cin.good());
a = M-M/3;
vector<vector<int>> G(N+4, vector<int>(M+4,2));
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> G[i+2][j+2];
}
}
assert(cin.good());
gioca(2, 2, G, 0);
cout << sol << endl;
}
) per non avere problemi quando controllo le caselle dei bordi. Semplicemente la funziona “gioca” controlla se è possibile aggiungere una “X” in una casella (i,j) iterando nella “matrice” in avanti da una casella iniziale (ix,jx), se si può aggiungere una “X” si richiama la funzione passando come casella iniziale da cui iterare quella successiva a dove si poteva mettere la “X” (N.B. non inserendo la x). Dopo la ricorsione si inserisce la “X” e si continua ad iterare. Alla fine la variabile globale sol assume il massimo valore tra sol e le x inserite. Scusate la spiegazione lunga ma volevo rendervi tutto chiaro 
, btw dov’è l’errore?
