Buonasera a tutti. Mi scuso per il fatto che questo è il secondo thread che apro in due giorni, ma sto cercando di ottenere un badge di diamante in tutte le categorie di algobadge.
Detto questo, stavo svolgendo solitario2 con il seguente codice, e gli ultimi testcase vanno quasi tutti in TLE, dandomi un punteggio di 50/100. Qualcuno riuscirebbe a darmi qualche suggerimento su come ottimizzare il tutto?
Il codice in questione:
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#pragma GCC optimize ("O3")
bool cercaTris(int i, int j, vector<vector<int>>& G){
if(G[i][j]==0){return false;}
return (G[i-2][j-2]==1&&G[i-1][j-1]==1&&G[i][j]==1)
||
(G[i-1][j-1]==1&&G[i][j]==1&&G[i+1][j+1]==1)
||
(G[i][j]==1&&G[i+1][j+1]==1&&G[i+2][j+2]==1)
||
(G[i-2][j+2]==1&&G[i-1][j+1]==1&&G[i][j]==1)
||
(G[i-1][j+1]==1&&G[i][j]==1&&G[i+1][j-1]==1)
||
(G[i][j]==1&&G[i+1][j-1]==1&&G[i+2][j-2]==1)
||
(G[i][j-2]==1&&G[i][j-1]==1&&G[i][j]==1)
||
(G[i][j-1]==1&&G[i][j]==1&&G[i][j+1]==1)
||
(G[i][j]==1&&G[i][j+1]==1&&G[i][j+2]==1)
||
(G[i-2][j]==1&&G[i-1][j]==1&&G[i][j]==1)
||
(G[i-1][j]==1&&G[i][j]==1&&G[i+1][j]==1)
||
(G[i][j]==1&&G[i+1][j]==1&&G[i+2][j]==1)
;
}
int gioca(const int n, const int m, int i, int j, vector<vector<int>> G){
int a=0,b=0;
if(i==n){
return 0;
}
if(j<m){
if(G[i][j]!=1){
G[i][j]=1;
if(!cercaTris(i,j,G)){
a=gioca(n,m,i,j+1,G)+1;
}
G[i][j]=0;
b=gioca(n,m,i,j+1,G);
}else{
a=gioca(n,m,i,j+1,G);
}
return a>b ? a : b;
}else{
return gioca(n,m,i+1,2,G);
}
}
int main()
{
ifstream fin("input.txt");
ofstream fout("output.txt");
int N, M;
fin >> N >> M;
vector<vector<int>> G(N+4, vector<int>(M+4,0));
//vector<vector<int>> memo(N+4, vector<int>(M+4, -1));
for(int i=2; i<N+2; i++){
for(int j=2; j<M+2; j++){
fin>>G[i][j];
//cin>>G[i][j];
}
}
//stampa(G);
//cout << gioca(N, M, G) << endl;
fout << gioca(N+2, M+2,2, 2, G) << endl;
fin.close();
fout.close();
}
Ringrazio in anticipo.