2094 - Blots on Paper

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?abb=2094

[HaZard]

Saludos, ¿alguien me puede decir qué tienen los casos de prueba de este ejercicio? lo he intentado de unas cuantas formas, con un mapa -> tiempo límite caso 12, con vectores -> Runtime Error caso 21, con uso de memoria dinamica -> Runtime Error caso 21, me tiene loco, gracias de antemano

[HaZard]

ya di con lo que era, ñooooooooo, que abuso, el runtime era porque estaba usando un dfs y al parecer daba internamente stack overflow, cambie el recorrido por un bfs y pum ya aceptado, aunque no se esta "discriminacion" con el dfs por qué JEJE, pero bueno, revisé las soluciones y todas las que vi usaban cola, saludos

[humbertodiaz]

Es peligroso usar DFS implementado recursivamente. Es comun que un recorrido pueda cubrir todos los elementos de un grafo o lo que sea que se este examinando, y si es suficientemente grande, se acaba el stack. Podrias implementar DFS con un contenedor explicito pero en muchos casos BFS con un queue funciona igual y tiene algunas propiedades que lo hacen preferible.