SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Jepthe en Sábado 3 de Julio de 2010, 22:04

Título: como hago un algoritmo para recorrer un laberinto!
Publicado por: Jepthe en Sábado 3 de Julio de 2010, 22:04

hola! en la universidad me mandaron la siguiente tarea en lenguaje de programacion, la de encontrar en un laberinto de 0 y 1(los 0 son caminos y los 1 paredes), todos los caminos posibles (de izquierda a derecha), sin devolverse, es decir solo hacia delante, puedo ir hacia arriba o abajo; despues de encontrar los caminos, mostrar el mas corto, y despues mostrar todos los caminos que empezaron pero no tienen salida; eso.... pero me ponen algunas condiciones solo puedo hacer uso de arreglos no de estructuras, el uso de los ciclos de control es ilimitado y eso, aaaa y el laberinto esta en un archivo txt y es de 20x19(en teoria era de 20x20 pero el profesor se pifio con una columna...jahahah...xD), bueno necesito toda la ayuda posible que me puedan brindar, cuando lleguen respuestas vere si estan dentro de lo que me pueda aceptar el profesor...pero cualquier ayuda en cualquier parte de las 3 metas me sirve... les dejo aca el laberinto...

Citar

1000000000000001000
0011111111111100011
1111111111111111111
0001000100011111111
1110010001011000001
0001111110100011100
1100001111000101010
0001100000010111111
0110011111010101010
0000111111110000000
1111111111111111111
0001011111111111111
1100011111111111111
1111110000000000000
0010000111111111111
1000111111111111111
1111111111100001111
0000000000001100000
1111111111110001111
1000000000000111111

desde ya muchas gracias..aaa otra cosa mi plazo para entregar este programa en c, es hasta el viernes 9 de julio...

Título: Re: como hago un algoritmo para un laberinto!
Publicado por: luchojimenez en Sábado 3 de Julio de 2010, 23:28

hombre  eso sale  con la libreria conio.h de  borland ,debes  aportar  algo de codigo para clarificar la idea

Título: Re: como hago un algoritmo para un laberinto!
Publicado por: luchojimenez en Domingo 4 de Julio de 2010, 04:10

es  facil, y asi para todos lo demas

Código: C++

1.  
2. #include<iostream>
3. using namespace std;
4. int main()
5. {
6. cout<<"1000000000000000000100000"<<endl;
7. system("pause");
8. return 0;
9. }
10.  
11.  
12.  

Título: Re: como hago un algoritmo para un laberinto!
Publicado por: Jepthe en Domingo 4 de Julio de 2010, 04:31

aca pongo lo que llevo hecho eso si tiene un pequeño error que no he podido corregir y es que me imprime un camino que no corresponde ademas de dos espacios en el lado izquierdo, si alguien sabe como corregirlo que me ayude.

Citar

#include <stdio.h>
#include <stdlib.h>
#include <conio2.h> //para compilarla hay que instalar la libreria conio.h y despues ir a herramientas, opciones de compilador, añadir estos comandos a la linea de comandos linker y escribir -lconio
#define columna 19  //se definen variables globales para hacer uso en cualquier parte del programa sin problema (incluso en funciones)
#define fila 20  //se definen variables globales para hacer uso en cualquier parte del programa sin problema (incluso en funciones)

int i = 0, j = 0;
int arreglo[fila][columna];
int contador1 = 0, contador2 = 0, contadorcero = 0;   // contador1 es el numero de direcciones, contador2 sirve como bandera para el do, contadorcero sirve para determinar el numero de pasadas
char b;

main(){

   textcolor(10); //modifica el color de las letras
   textbackground(0); //modifica el color de fondo

// va a leer el archivo y lo que encuentre lo va a guardar en la matriz

FILE *pf;

   if(( pf = fopen("laberinto.txt","r")) == NULL )    
      printf("nNo esta el archivo !"); // se imprime esto si el archivo txt no esta en la misma carpeta que el programa

   else
      do{ // como while valida la condicion antes de ejecutar no toma la ultima posicion del arreglo, por eso se reemplaza por do while que ejecuta la accion y luego valida tomando asi el ultimo valor del arreglo
         fscanf(pf,"%c",&b);

         if( b == '0' ){
            arreglo[j] = 0;
            i=i+1;
                contadorcero=contadorcero+1;
         }

         else{
            arreglo[j] = 1;
            i=i+1;;
         }

         if( i >= columna + 1 ){
                j=j+1;
                i = 0;
            }

      }while( !feof(pf)); //funcion (de manejo de archivos) retorna verdadero cuando llega al final del archivo, como esta negado cuando llege al final retornara falso y terminara el ciclo
   fclose(pf);
system("cls");

   contadorcero = contadorcero/3; // Determina el numero de pasadas

   // Aqui es donde elimina los caminos hasta llegar al mas optimo

  do{
   for( j = 1; j < fila-1; j++ ){
      for( i = 1; i < columna-1; i++){

         if( arreglo[j] == 0 ){

            if( arreglo[j][i-1] == 0 )
                   contador1=contador1+1;

            if( arreglo[j-1] == 0 )
                   contador1=contador1+1;

            if( arreglo[j][i+1] == 0 )
                   contador1=contador1+1;

            if( arreglo[j+1] == 0 )
                   contador1=contador1+1;
         }
         if( contador1 < 2 )
               arreglo[j] = 1;
            contador1=0;
      }
   }
   contador2=contador2+1;

  }while( contador2 < contadorcero );

   // Muestra el resultado

   for( j = 0; j < fila; j++ ){
      for( i = 0; i < columna; i++){

         if(arreglo[j] == 0){
            gotoxy( i+1,j+1); //es una funcion de <conio2.h> y se usa para posicionar en unas cordenadas lo que se imprime
                cprintf(" "); //imprime la letra con el color definido anteriormente
         }

         else{
            gotoxy( i+1,j+1); //es una funcion de <conio2.h> y se usa para posicionar en unas cordenadas lo que se imprime
                cprintf("Û"); //imprime la letra con el color definido anteriormente
         }
      }
   }
   getch(); // usado para leer el archivo
    getch(); // usado para leer el archivo
}