Asuntos Oficiales > Retos
18/04/2004 : Braid Theory (dificultad Media)
Nagisa:
Veamos... La primera entrada no seria posible, ya que el dibujo no esta cerrado.
Sobre el caso de que un '+' forme parte de varios lazos.... auqnue del enunciado no se deduce, la respuesta es que no. En tu segundo ejemplo... cual seria la solucion correcta?? 1 o 2?? Digamos que eso entraria en el caso de "lazo ambiguo".
patitofeo:
La respuesta seria: 2.
--- Código: Text --- +---+ | | | | | | +-------+ | | | | +---+
si fuese 1 seria asi: con un '-' o un '|'. ¿no es asi?
De todas formas, si estas entradas no son posibles se facilita el problema.
Igual me pongo este fin de semana y lo intento resolver.
Nagisa:
Veamos... la respuesta depende de como soluciones el problema , y ambas serian aceptables!! Por eso se descartan esas entrada, por ser ambiguas.
Bien... debido a los examenes no he podido optimizar en absoluto la solucion, la cual se puede mejorar por muchos sitios.
Explicando a groso modo, el problema se reduce a uno de contar componentes conexas en un grafo, el cual viene dado por la entrada.
Cuando hablo de mis posibles optimizaciones son a la hora de representar dicho grafo y el algoritmo de contado (cuando escribi el codigo todavia no sabia hacerlo).
Aqui cada nodo del grafo es un registro con 4 punteros y un valor que lo identifica exclusivamente.
El algoritmo de recorrido es destructivo (etiqueta los nodos visitados con un 0), y se aprovecha de que sabemos que ningun nodo tiene grado mayor que 2. Escojo un nodo valido (id != 0); una vez llego a un nodo, solo tengo un posible camino para seguir , por lo tanto lo marco (id = 0) y reitero por el siguiente ; si no, termino con esa componente conexa, la cuento y busco un nuevo nodo
Tira con el gcc, asi que no creo que tengais problemas. Lo adjunto como .txt por que no me deja hacerlo como .c
De todas formas, si hay cualquier duda, preguntadla :D
Navegación
[*] Página Anterior
Ir a la versión completa