Hola, buenas a todos. Estaba resolviendo el problema ¿Cuán uniforme es la imagen? del certamen nacional del 2012, nivel 2 (http://juez.oia.unsam.edu.ar/#/task/uniformar/statement) y logré, después de dar vueltas con varias ideas, a un puntaje de 95/100.
Resulta que un único caso se pasa del tiempo estipulado. Pero lo llamativo es la gran cantidad de memoria que consume (≃250MB) en comparación con el resto de los casos (6 MB como mucho). Por dicha razón, creo que hay un caso en la cual mi código se queda trabado en un loop infinito, acumulando valores en alguna variable o estructura de datos indefinidamente.
Lo estuve cambiando y pensando las razones, viendo si puse alguna cota mal o algo que podría haber llegado a que algún iterador no finalice su tarea o situaciones similares, pero no logro llegar a una solución.
Me gustaría saber si alguno sabe cuál es problema:
Código
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i<int(n); i++)
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> ii;
typedef vector<vector<bool> > vbo;
const int xr[4] = {0,-1,0,1};
const int yr[4] = {1,0,-1,0};
vector<string> mat;
vbo done;
int r = 0;
bool unif = false;
vector<ii> pos = {{0,0}};
bool valid(int i, int j) {
if (i >= mat.size() or i < 0) return false;
if (j >= mat.size() or j < 0) return false;
return true;
}
void bfs() {
queue<ii> Q;
r++;
if (pos.empty()) {
unif = true;
return;
}
while(!pos.empty()) {
ii x = pos.back();
Q.push(x);
done[x.fst][x.snd] = true;
pos.pop_back();
}
while (not Q.empty()) {
ii x = Q.front(); Q.pop();
int i = x.fst, j = x.snd;
forn (k, 4) {
int ni = i+yr[k], nj = j+xr[k];
if (!(valid(ni,nj))) continue;
if (done[ni][nj]) continue;
if (mat[ni][nj] != mat[i][j]) {
pos.push_back({ni,nj});
}
else {
done[ni][nj] = true;
Q.push({ni,nj});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("uniformar.in","r",stdin);
freopen("uniformar.out","w",stdout);
int N;
cin >> N;
done.resize(N+2,vector<bool>(N+2,false));
forn (i,N) {
string x;
cin >> x;
mat.push_back(x);
}
while (!unif)
bfs();
cout << r-2 << endl;
return 0;
}
Para ayudar a entender el código mejor, describo brevemente el procedimiento que realizo ahí:
- Empiezo a reorrer la matriz dada desde la posición (0,0) con un BFS en grilla, en busca de sólo aquellos números que sean igual al adyacente del cual parto con cada vuelta de sacar del queue.
- Si se cumple la condición lo marco hecho. De lo contrario lo guardo aparte. (Aclaro que no vuelvo a pasar por aquellos que marqué hechos)
- Ejecuto el BFS la próxima vez con todos los elementos que guardé antes en el queue, que eran distintos del cual partía en la pasada anterior…así sucesivamente hasta que no tenga más valores en donde guardo los valores distintos.
- Por cada vez que uso el BFS, le sumo 1 al resultado (al final debo de restarle al resultado un par de vueltas, por la forma en que sumo y hago los chequeos para parar).
Espero puedan ayudarme. Muchas gracias.