Sto provando a risolvere trendytrash, ma il codice va fuori tempo in 3 o 4 testcases dell’ultimo subtask. Ho provato ad aggiungere quante più ottimizzazioni mi venissero in mente, ma il risultato rimane sempre lo stesso. Voi sapreste dirmi qualche possibile miglioramento?
#include <bits/stdc++.h>
using namespace std;
// total all'inizio è il numero di sacchetti, poi diventa il risultato
int tot, tolto_temp, tolto;
int check_colonna(int N, int M, int r, int c, vector<string> &S, int righe[]) {
int i, counter = 0;
for(i=r; i<N-1; i++) {
// controlla che l'elemetno non sia segnato nel vettore, se si saltalo
if(righe[i] == 1) {
continue;
}
// controlla la (in)validità della posizione in cui ci troviamo
if(S[i][c] != S[r][c]) return 0;
// è l'elemento che ho tolto nel loop precedente, non serve controllare
if(tolto != -1 && tolto != 2 && tolto == S[i][c]-48) return 0;
counter++;
}
// siamo alla fine della linea
// controllo che l'ultimo sacchetto non sia escluso
if(righe[i] != 1) counter++;
// controlla che sia valido l'elemento in cui ti trovi
if(righe[i] != 1 && S[i][c] != S[r][c]) return 0;
// update del totale
tot -= counter;
// ottimizzazione
// in questo loop non ho ancora tolto nessun sacchetto
if(tolto_temp == -1) tolto_temp = S[r][c] - 48;
// ho tolto sia 1 che 0 (entrambi i sacchetti)
else if (tolto_temp != S[r][c]) tolto_temp = 2;
return 1;
}
int check_riga(int N, int M, int r, int c, vector<string> &S, int colonne[]) {
int i, counter = 0;
for(i=c; i<M-1; i++) {
// controlla che l'elemetno non sia segnato nella vettore, se si saltalo
if(colonne[i] == 1) {
continue;
}
// controlla la (in)validità della posizione in cui ci troviamo
if(S[r][i] != S[r][c]) return 0;
// è l'elemento che ho tolto nel loop precedente, non serve controllare
if(tolto != -1 && tolto != 2 && tolto == S[r][i]-48) return 0;
counter++;
}
// siamo alla fine della linea
// controllo che l'ultimo sacchetto non sia escluso
if(colonne[i] != 1) counter++;
// controlla che sia valido l'elemento in cui ti trovi
if(colonne[i] != 1 && S[r][i] != S[r][c]) return 0;
// update del totale
tot -= counter;
// ottimizzazione
// in questo loop non ho ancora tolto nessun sacchetto
if(tolto_temp == -1) tolto_temp = S[r][c] - 48;
// ho tolto sia 1 che 0 (entrambi i sacchetti)
else if (tolto_temp != S[r][c]) tolto_temp = 2;
return 1;
}
int pulisci(int N, int M, vector<string> S) {
tot = N*M;
int righe[N] = {}, colonne[M] = {};
int c_r = 1, c_c = 1, ri = 0, ci = 0, temp_c, temp_r;
tolto = -1, tolto_temp = -1;
while(c_r == 1 || c_c == 1) {
// copio le variabili, mi servono per risparmiare tempo. Se ho tolto solo righe controllo solo le colonne e viceversa
temp_c = c_c;
temp_r = c_r;
// reset variabili di controllo
c_r = 0, c_c = 0;
// variabile di controllo per trovare la prima riga / colonna agibile
int controllo = 0;
// ho tolto almeno una colonna nel loop precedente, controllo le righe
if(temp_c == 1) {
for(int i=ri; i<N; i++) {
// conotrollo che quetsa riga non sia già eliminata
if(righe[i] == 1) continue;
// controllo se = 1 ho tolto la riga, faccio update
if(check_riga(N, M, i, ci, S, colonne) == 1) {
righe[i] = 1;
// questa variabile è = 0 all'inizio del loop e cambia solo
// se sposto almeno un sacchetto
c_r = 1;
}
// prendo la prima riga agibile, da utilizzare nel prossimo loop
else if(controllo == 0) {
ri = i;
controllo = 1;
}
}
}
// variabile di controllo per trovare la prima riga / colonna agibile
controllo = 0;
// ho tolto almeno una riga nel loop precedente, controllo le colonne
if(temp_r == 1) {
for(int h=ci; h<M; h++) {
// conotrollo che quetsa colonna non sia già eliminata
if(colonne[h] == 1) continue;
// controllo se = 1 ho tolto la colonna, faccio update
if(check_colonna(N, M, ri, h, S, righe) == 1) {
colonne[h] = 1;
// copio in questa variabile, che è = 0 all'inizio del loop e cambia solo
// se sposto almeno un sacchetto
c_c = 1;
}
else if(controllo == 0) {
ci = h;
controllo = 1;
}
}
}
// salvo la variabile per il loop successivo
tolto = tolto_temp;
}
return tot;
}