Buongiorno, ho scritto il codice per risolvere solitario2 generando una matrice con un bordo=2 ma purtroppo ricevo 10 punti su 100 per output errato a causa del primo caso base e anche qualche TLE. Rimuovendo il primo caso base ricevo 50 punti, quindi deduco che il problema sia lì, ma davvero non riesco a capire come sistemarlo, avete qualche idea? Questo è il codice.
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;
int sol=0;
int area;
inline bool check(int r,int c, vector<vector<int>>mat){
if(mat[r][c]) return false;
if(mat[r-1][c]+mat[r-2][c]>1) return false;
if(mat[r-1][c]+mat[r+1][c]>1) return false;
if(mat[r+1][c]+mat[r+2][c]>1) return false;
if(mat[r][c-1]+mat[r][c-2]>1) return false;
if(mat[r][c-1]+mat[r][c+1]>1) return false;
if(mat[r][c+1]+mat[r][c+2]>1) return false;
if(mat[r-1][c-1]+mat[r-2][c-2]>1) return false;
if(mat[r-1][c-1]+mat[r+1][c+1]>1) return false;
if(mat[r+1][c+1]+mat[r+2][c+2]>1) return false;
if(mat[r-1][c+1]+mat[r-2][c+2]>1) return false;
if(mat[r-1][c+1]+mat[r+1][c-1]>1) return false;
if(mat[r+1][c-1]+mat[r+2][c-2]>1) return false;
return true;
}
void rec(int r,int c,int val,int N, int M, vector<vector<int>> &G){
int esplorate=N*r+c;
if((area-esplorate)*0.67+val<sol) return; //CASO BASE se piazzo x nei 2/3 delle caselle rimaste il valore che ottengo è minore del massimo che ho trovato fin ora
if(r==N-1 && c==M-1) { //CASO BASE se ho esplorato tutta la matrice
sol=val>sol ? val:sol;
return;
}
if(c==M-1){ //se sono arrivato all'ultima cella della riga
rec(r+1,0,val,N,M,G); //non piazzo la x
if(check(r+3,2,G)){ //se posso piazzare la x
G[r+3][2]=1;
rec(r+1,0,val+1,N,M,G);//piazzo la x
G[r+3][2]=0;
}
}
else {
//cout<<check(r+2,c+3,N,M,G)<<endl;
rec(r,c+1,val,N,M,G); //non piazzo la x
if(check(r+2,c+3,G)){ //se posso piazzare la x
G[r+2][c+3]=1;
rec(r,c+1,val+1,N,M,G);//piazzo la x
G[r+2][c+3]=0;
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int N, M;
cin >> N >> M;
area=N*M;
int basex=0;
vector<vector<int>> G(N+4,vector<int>(M+4));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin>>G[i+2][j+2];
if(G[i+2][j+2])basex++;
}
}
rec(0,0,basex,N,M,G);//non piazzo la x nella prima casella
if(check(2,2,G)){ //se posso piazzarla
G[2][2]=1;
rec(0,0,basex+1,N,M,G);//piazzo la x
}
/*for(int i=0;i<N+4;i++){
for(int j=0;j<M+4;j++)cout<<G[i][j]<<" ";
cout<<endl;
}*/
cout << sol-basex << endl;
}