2094 - Blots on Paper

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2094 - Blots on Paper

Post by ymondelo20 » 7 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2094 - Blots on Paper

Post by HaZard » 5 years ago

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
teruel

HaZard
Posts: 114
Joined: 6 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2094 - Blots on Paper

Post by HaZard » 5 years ago

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
Last edited by HaZard on Fri Dec 05, 2014 7:24 pm, edited 1 time in total.
teruel

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 2094 - Blots on Paper

Post by humbertodiaz » 5 years ago

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.

Post Reply

Return to “Problem set”