SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: Epa en Miércoles 18 de Abril de 2007, 05:44
-
Buenas a todos.
Anod tratando de resolver esto hace mucho tiempo y me esta comiendo la cabeza. Tras horas y horas de pruebas obtube algunos datos, pero no puedo llegar al resultado. Asique decidi preguntar si alguin save la respuesta.
Necesito un algoritmo que resuelva cuantos caminos posibles hay de una punta de una matriz a la otra, avanzando de uno en uno y sin volver hacia atras.
Por ejemplo en una matriz de 5 x 5 hay 66 caminos.
**000
0*000
0***0
000*0
000**
Ese es uno, para dar un ejemplo y que se entienda.
Si es de utilidad, calcule los caminos hasta matrices de 9 x 9
2 x 2 = 2
3 x 3 = 6
4 x 4 = 20
5 x 5 = 66
6 x 6 = 216
7 x 7 = 704
8 x 8 = 2292
9 x 9 = 7470
Bueno, espero alguien pueda darme una mano.
Les agradesco de antemano.
Saludos :hola:
-
Eso me suena a un DFS (http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad) adaptado desde el nodo inicial y que contabilice el número de veces que se llega al nodo destino.
Luis Javier López Arredondo
-
Buenas
No entendi el ejemplo ya que no se pseudocodigo :P sin embargo el concepto me quedo claro. Asique voy a intentar aplicarlo aver que sale. :D
Muchas gracias
Saludos
-
Lo que cuenta es la idea. Básicamente es visitar todos los nodos hijos del nodo actual antes de visitar sus nodos hermanos, controlando los que ya han sido visitados. Lo del DFS es una guía, seguro que Google puede ayudar más que yo.
Un saludo.
Luis Javier López Arredondo