SoloCodigo
Programación General => C/C++ => Mensaje iniciado por: jhernandezr en Sábado 10 de Julio de 2010, 01:02
-
Antes que todo disculpen, pero no se como empezar con el siguiente programa...
Las verdad es que se me ocurren algunas ideas, pero no se como materializarlas en codigo...
Les agradeceria si pudieran ayudarme con algunas lineas de para el siguiente programa:
Debes escribir un programa que lea una matriz de 4 filas y 20 columnas desde teclado,
luego debes imprimir la matriz leida y finalmente imprimir las coordenadas del camino de
elementos iguales a cero que encuentres en la matriz desde la columna 0 a la 19. Los demas
elementos de la matriz son "unos".
Ejemplos de matrices:
Ej1:
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Ej2:
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1
- Solo hay un camino de ceros que empieza en la columan 0 y termina en la 19
- Los caminos tienen "curvas" de noventa grados.
- Siempre hay un camino.
- Los caminos siempre dejan al menos un '1' antes de "doblar" a la proxima fila
- No hay cambio de fila en la columna cero.
- Los "caminos" son generados en forma aleatoria
Ejemplo:
si los valores leidos por teclado son:
1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
tu programa debe imprimir:
1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1
0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
1,0
1,1
0,1
0,2
0,3
1,3
1,4
1,5
0,5
0,6
0,7
0,8
1,8
1,9
1,10
1,11
0,11
0,12
0,13
1,13
1,14
1,15
2,15
2,16
2,17
3,17
3,18
3,19
:(
-
En realidad es bastante sencillo:
Primero buscas un cero en la primera columna, guardas la posición
Haces esto hasta que la posición guardada esté en la columna final:
* Marcar la posición como recorrida, por ejemplo poner un 2.
* Imprimir coordenada
* Buscar una casilla aledaña que sea 0, guardar su posición
-
Necesitas usar un metodo llamado backtraking
-
:no: No se necesita usar backtracking ya que solo hay un camino en la matriz.
-
se puede usar un metodo de busqueda parecido al backtraking buscandp la primera solucion ya que solo es un camino pero tiene muchas opciones para ser candidato a un camino o puede que no exista camino, la idea es usar como analogia el problema del laberinto xD B)