Sto uscendo pazzo. Dopo tanto tempo sono ritornato su questo problema che prima mi sembrava impossibile, e ho tirato fuori questo codice:
pair<int, int> sceglinodi(char a, char b){
if(a == b){
if(a == '/') return {1, 0};
return {0, 1};
}
if(a == '/') return {1, 1};
return {0, 0};
}
void dfs(int a, bool visited[], vector<int> adj[]){
for (auto u : adj[a]) {
if (visited[u]) continue;
visited[u] = true;
dfs(u, visited, adj);
}
}
int main(){
fast();
/* freopen("output.txt", "r", stdin);
freopen("slashout.txt", "w", stdout); */
int x, y; cin >> x >> y;
int x2 = x*2;
int nodi = x2 * y;
vector<int> adj[nodi] = {}; //adj[nodo attuale] = nodo di arrivo
pair<int, int> sotto(0, 0);
int sopra;
char oldx, temp;
for(int i = 0; i < x; i++){
cin >> oldx;
for(int j = 1; j < y; j++){
cin >> temp;
sotto = sceglinodi(oldx, temp);
sopra = ((j-1) * x2 + (2*i));
int a = sopra + sotto.first, b = sopra + x2 + sotto.second;
adj[a].push_back(b); //nodi orizzontali
adj[b].push_back(a);
if(i != x-1){
a = sopra + 1; b = sopra + 2;
adj[a].push_back(b); //nodi verticali
adj[b].push_back(a);
}
oldx = temp;
}
if(i != x-1){
int a = sopra + x2 + 1, b = sopra + x2 + 2;
adj[a].push_back(b); //nodi verticali
adj[b].push_back(a);
}
}
bool visited[nodi] = {false};
int sol = 0;
for(int i = 0; i < nodi; i++){
if(visited[i]) continue;
visited[i] = true;
dfs(i, visited, adj);
sol++;
}
cout<<sol;
return 0;
}
Bene, l’idea dietro è quella di crearsi una lista di adiacenza e, con molta pazienza, crearsi 2 nodi per ogni slash che hanno archi verso i nodi vicini . Funziona tutto perfettamente. Peccato per 2 testcase che mi danno “execution killed”, e non capisco se davvero si tratta di memoria o no. Suppongo di si essendo che ho provato testcase alti, e se n, m > 201 l’algoritmo crasha. Chiedo solo, devo buttare l’algoritmo? o ci sono modi di ottimizzare la memoria in questo caso?
test cases errati:
