SoloCodigo

Programación General => Java => Mensaje iniciado por: kurtjavier en Martes 9 de Febrero de 2010, 03:13

Título: ¿ Camino mas corto en un Laberinto ?
Publicado por: kurtjavier en Martes 9 de Febrero de 2010, 03:13
Ok, explic ode una: Me mandaron a hacer un laberinto, leido desde un archivo de texto, que mostrara todos los caminos posibles desde un punto de salida hasta un punto de llegada,  y pintara todos los distintos caminos y luego señalara el camino mas corto.

¿Que es lo que he hecho?
como es con interfaz grafica tuve que hacerlo en java (aunque me inclino por el  c++ pero bueno), para cada casilla hice una clase llamada CASILLA que me hereda de JTextField, esto lo hice para pintar y representar mejor la interfaz. Tengo una clase Laberinto con mi arreglo de casillas (las dimensiones del laberinto), y en este tengo un metodo que me busca un camino, por ahoroa solo he logrado que me busque un camino, mi problema no es que me busque un camino poque ya lo hice, el problema es que necesito que ese camino sea el mas corto, como puedo hacer para determinar cual es el camino mas corto entre los dos puntos. El laberinto es cargado desde un archivo de texto donde * representa camino y # pared, cuando leo el archivo cargo las dimensiones inicializo mi arreglo de casillas pinto la interfaz y el usuario señala los putos de partida y llegada con el mouse, cuando le da a un boton llamo al metodo SOLUCIONAR q me busca el camino.

Como ya dije solucione que encontrara un camino, de hecho puedo conseguir todos los caminos ya que camino recorrido es marcado para q no sea recorrido nuevamente por otro camino nuevo que se vaya a hacer, pero quisiera que el primer camino que me mostrara fuera el mas corto, mi pregunta es como hago para saber cual es el camino mas corto. Aqui dejo la clase CASILLA, LABERINTO.

Clase casilla
Código: Java
  1.  
  2.  
  3. import javax.swing.JTextField;
  4. import java.awt.Color;
  5.  
  6. public class casilla extends JTextField
  7. {
  8.  
  9.     private char tipo;
  10.     private boolean recorrida,norecorrida;
  11.     private short id_Unico;
  12.  
  13.     casilla()
  14.     {
  15.         super();
  16.         tipo='-';
  17.         recorrida=false;
  18.         norecorrida=false;
  19.         id_Unico=0;
  20.         this.setEditable(false);
  21.         this.setBackground(Color.WHITE);
  22.     }
  23.  
  24.     casilla(short ii)
  25.     {
  26.         super();
  27.         tipo='*';
  28.         recorrida=false;
  29.         norecorrida=false;
  30.         id_Unico=ii;
  31.         this.setEditable(false);
  32.         this.setBackground(Color.WHITE);
  33.     }
  34.  
  35.     casilla(char t)
  36.     {
  37.         tipo=t;
  38.         recorrida=false;
  39.         norecorrida=false;
  40.         id_Unico=0;
  41.         this.setEditable(false);
  42.         this.setBackground(Color.WHITE);
  43.     }
  44.  
  45.     public void setTipo(char t){    tipo=t; }
  46.     public void setRecorrida(boolean r){    recorrida=r;    }
  47.     public void setNoRecorrida(boolean r){  norecorrida=r;  }
  48.     public void setID(short id){    id_Unico=id;    }
  49.    
  50.     public char getTipo(){  return tipo;    }
  51.     public boolean getRecorrida(){  return recorrida;   }
  52.     public boolean getNoRecorrida(){    return norecorrida; }
  53.     public short getID(){   return id_Unico;    }
  54. }
  55.  
  56.  
  57.  


Clase Laberinto
Código: Java
  1.  
  2.  
  3. import java.awt.Color;
  4.  
  5. class laberinto {
  6.  
  7.     private casilla[][] lab;
  8.     private int n;
  9.  
  10.     laberinto(int x)
  11.     {
  12.         this.n=x;
  13.         lab=new casilla[x][x];
  14.     }
  15.  
  16.     public casilla[][] getLaberinto(){  return lab; }
  17.     public casilla getCasilla(int i, int j){    return lab[i][j];   }
  18.  
  19.     public void setLaberinto(casilla[][] lab2){ lab=lab2;   }
  20.     public void setCasilla(casilla c,int x, int y){ lab[x][y]=c;    }
  21.    
  22.     public void setFalso(casilla inicio, casilla fin)
  23.     {
  24.         for(int i=1;i<n;i++)
  25.         {
  26.             for (int j=1;j<n;j++)
  27.             {
  28.                 lab[i][j].setRecorrida(false);
  29.                 lab[i][j].setNoRecorrida(false);
  30.                 if(lab[i][j]!=inicio && lab[i][j]!=fin)
  31.                     lab[i][j].setBackground(Color.WHITE);
  32.             }                  
  33.         }
  34.     }
  35.    
  36.     boolean solucionar(casilla posicion, casilla anterior, casilla fin, int fila, int columna)
  37.     {
  38.         lab[fila][columna].setRecorrida(true);
  39.         lab[fila][columna].setNoRecorrida(true);
  40.         if(posicion==fin)
  41.             return true;
  42.         boolean encontrado=false;
  43.         //abajo
  44.         if(fila+1 < n)
  45.         {
  46.             if(!lab[fila+1][columna].getNoRecorrida() && lab[fila+1][columna]!=anterior && lab[fila+1][columna].getTipo()!='#')
  47.             {
  48.                 encontrado=solucionar(lab[fila+1][columna],lab[fila][columna],fin,fila+1,columna);
  49.                 if(encontrado)
  50.                 {
  51.                     return true;
  52.                 }
  53.                 lab[fila+1][columna].setNoRecorrida(true);
  54.                 lab[fila+1][columna].setRecorrida(false);
  55.             }
  56.         }
  57.         //derecha
  58.         if(columna+1 < n)
  59.         {
  60.             if(!lab[fila][columna+1].getNoRecorrida() && lab[fila][columna+1]!=anterior && lab[fila][columna+1].getTipo()!='#')
  61.             {
  62.                 encontrado=solucionar(lab[fila][columna+1],lab[fila][columna],fin,fila,columna+1);
  63.                 if(encontrado)
  64.                 {
  65.                     return true;
  66.                 }
  67.                 lab[fila][columna+1].setNoRecorrida(true);
  68.                 lab[fila][columna+1].setRecorrida(false);
  69.             }
  70.         }
  71.         //arriba
  72.         if(fila-1 > 0)
  73.         {
  74.             if(!lab[fila-1][columna].getNoRecorrida() && lab[fila-1][columna]!=anterior && lab[fila-1][columna].getTipo()!='#')
  75.             {
  76.                 encontrado=solucionar(lab[fila-1][columna],lab[fila][columna],fin,fila-1,columna);
  77.                 if(encontrado)
  78.                 {
  79.                     return true;
  80.                 }
  81.                 lab[fila-1][columna].setNoRecorrida(true);
  82.                 lab[fila-1][columna].setRecorrida(false);
  83.             }
  84.         }
  85.         //izquierda
  86.         if(columna-1 > 0)
  87.         {
  88.             if(!lab[fila][columna-1].getNoRecorrida() && lab[fila][columna-1]!=anterior && lab[fila][columna-1].getTipo()!='#')
  89.             {
  90.                 encontrado=solucionar(lab[fila][columna-1],lab[fila][columna],fin,fila,columna-1);
  91.                 if(encontrado)
  92.                 {
  93.                     return true;
  94.                 }
  95.                 lab[fila][columna-1].setNoRecorrida(true);
  96.                 lab[fila][columna-1].setRecorrida(false);
  97.             }
  98.         }
  99.         lab[fila][columna].setRecorrida(false);
  100.         return false;
  101.     }
  102. }
  103.  
  104.  


Ayuda por fa, esto es para el miercoles ya hoy es lunes tengo ya 4 dias dando golpes aqui y q va no me da mas el cerebro por mi cuenta necesito ayuda definitivamente jaja......
Título: Re: ¿ Camino mas corto en un Laberinto ?
Publicado por: fjmc22 en Martes 9 de Febrero de 2010, 13:08
haber si te sirve este ejemplo que tenia hecho de un ejercicio de backtraking

Código: Java
  1. public class Laberinto
  2. {
  3.    public static boolean hayCamino (char[][] laberinto) {
  4.       int[] incrX = new int[] {1, 0, -1,  0};
  5.       int[] incrY = new int[] {0, 1,  0, -1};
  6.       laberinto[0][0] = 'C';
  7.       boolean exito = buscar (laberinto.length-1, 0, 0, laberinto, incrX, incrY);
  8.       imprimir (laberinto);
  9.       return exito;
  10.    }
  11.    private static boolean buscar (int n_1,
  12.                                   int x,
  13.                                   int y,
  14.                                   char[][] laberinto,
  15.                                   int[] incrX,
  16.                                   int[] incrY) {
  17.       boolean exito = false;
  18.       for (int k=0; k<4 && !exito; k++) {
  19.          int coordX = x + incrX[k];
  20.          int coordY = y + incrY[k];
  21.          if (coordX>=0 && coordX<=n_1 &&
  22.              coordY>=0 && coordY<=n_1)
  23.             if (laberinto[coordY][coordX] == ' ') {
  24.                laberinto[coordY][coordX] = 'C';
  25.                if (coordX==n_1 && coordY==n_1)
  26.                   exito = true;
  27.                else {
  28.                   exito = buscar (n_1, coordX, coordY, laberinto, incrX, incrY);
  29.                   if (!exito)
  30.                      laberinto[coordY][coordX] = ' ';
  31.                }
  32.             }
  33.       }
  34.       return exito;
  35.    }
  36.    
  37.     private static void imprimir (char[][] laberinto) {
  38.       for (int i=0; i<laberinto.length; i++) {
  39.          for (int j=0; j<laberinto.length; j++)
  40.             System.out.print (laberinto[i][j]+" ");
  41.          System.out.println();
  42.       }
  43.    }
  44. }
  45.  
  46.  
Título: Re: ¿ Camino mas corto en un Laberinto ?
Publicado por: nacheteibo en Jueves 18 de Febrero de 2010, 18:07
Hola buenas

sabeis como sería el codigo del laberitno para Fortran. Es que  estoy aprendiendo a programar en serio y con este ejercicio quiero a consolidar lo ya aprendido.

un saludo
Título: Re: ¿ Camino mas corto en un Laberinto ?
Publicado por: kurtjavier en Viernes 19 de Febrero de 2010, 00:17
Bueno gente hace dias que ya habia terminado el programa se me habia olvidado colocarlo aqui, les dejo la solucion, bueno la que le encontre yo, un laberinto en java usando backtracking, me guarda todos los caminos en una matriz y despues solo verifico cual es el mas corto y listo.

Código: Java
  1.  
  2.  
  3. /*
  4. Realizado por Francisco Gallucci */
  5.  
  6. import java.awt.Color;
  7.  
  8. class Laberinto {
  9.  
  10.     private Casilla[][] lab,solucion;
  11.     private int n,pix,piy,pfx,pfy,id_Solucion,max;
  12.  
  13.     Laberinto(Casilla[][] lab2, int x)
  14.     {
  15.         this.n=x;
  16.         max=n*n;
  17.         lab=new Casilla[x][x];
  18.         solucion=new Casilla[max][max];
  19.         lab=lab2;
  20.         id_Solucion=0;
  21.         pix=piy=pfx=pfy=0;
  22.     }
  23.  
  24.     public int getCaminoMasCorto()
  25.     {
  26.         int[] cantidad=new int[id_Solucion];
  27.         for(int i=0; i < id_Solucion ; i++)
  28.         {
  29.             cantidad[i]=0;
  30.             for(int j=0; solucion[i][j]!=null ;j++)
  31.                 cantidad[i]++;
  32.         }
  33.         int menor=0;
  34.         for(int j=0; j < id_Solucion;j++)
  35.             if( cantidad[j] < cantidad[menor])
  36.                 menor=j;
  37.         return menor;
  38.     }
  39.        
  40.     boolean solucionar(Casilla posicion, Casilla fin, int fila, int columna,int y_Sol)
  41.     {
  42.         if(posicion==fin)
  43.         {
  44.             lab[fila][columna].setRecorrida(false);
  45.             id_Solucion++;
  46.             return true;
  47.         }
  48.         lab[fila][columna].setRecorrida(true);
  49.         boolean encontrado=false;
  50.         //abajo
  51.         if(fila+1 < n && id_Solucion < max)
  52.         {
  53.             if(!lab[fila+1][columna].getRecorrida() && lab[fila+1][columna].getTipo()!='#')
  54.             {
  55.                 solucion[id_Solucion][y_Sol]=lab[fila][columna];
  56.                 encontrado=solucionar(lab[fila+1][columna],fin,fila+1,columna,y_Sol+1);
  57.                 if(encontrado)
  58.                 {
  59.                     if(id_Solucion < max-1)
  60.                     {
  61.                         int i=0;
  62.                         while(solucion[id_Solucion-1][i] != null )
  63.                         {
  64.                             solucion[id_Solucion][i]=solucion[id_Solucion-1][i];
  65.                             i++;
  66.                         }
  67.                     }
  68.                     encontrado=false;
  69.                 }
  70.                 else
  71.                 {
  72.                     solucion[id_Solucion][y_Sol+1]=null;
  73.                     lab[fila+1][columna].setRecorrida(false);
  74.                 }
  75.             }
  76.         }
  77.         //derecha
  78.         if(columna+1 < n && id_Solucion < max)
  79.         {
  80.             if(!lab[fila][columna+1].getRecorrida() && lab[fila][columna+1].getTipo()!='#')
  81.             {
  82.                 solucion[id_Solucion][y_Sol]=lab[fila][columna];
  83.                 encontrado=solucionar(lab[fila][columna+1],fin,fila,columna+1,y_Sol+1);
  84.                 if(encontrado)
  85.                 {
  86.                     if(id_Solucion < max-1)
  87.                     {
  88.                         int i=0;
  89.                         while(solucion[id_Solucion-1][i] != null )
  90.                         {
  91.                             solucion[id_Solucion][i]=solucion[id_Solucion-1][i];
  92.                             i++;
  93.                         }
  94.                     }
  95.                     encontrado=false;
  96.                 }
  97.                 else
  98.                 {
  99.                     solucion[id_Solucion][y_Sol+1]=null;
  100.                     lab[fila][columna+1].setRecorrida(false);
  101.                 }
  102.             }
  103.         }
  104.         //arriba
  105.         if(fila-1 > 0 && id_Solucion < max)
  106.         {
  107.             if(!lab[fila-1][columna].getRecorrida() && lab[fila-1][columna].getTipo()!='#')
  108.             {
  109.                 solucion[id_Solucion][y_Sol]=lab[fila][columna];
  110.                 encontrado=solucionar(lab[fila-1][columna],fin,fila-1,columna,y_Sol+1);
  111.                 if(encontrado)
  112.                 {
  113.                     if(id_Solucion < max-1)
  114.                     {
  115.                         int i=0;
  116.                         while(solucion[id_Solucion-1][i] != null )
  117.                         {
  118.                             solucion[id_Solucion][i]=solucion[id_Solucion-1][i];
  119.                             i++;
  120.                         }
  121.                     }
  122.                     encontrado=false;
  123.                 }
  124.                 else
  125.                 {
  126.                     solucion[id_Solucion][y_Sol+1]=null;
  127.                     lab[fila-1][columna].setRecorrida(false);
  128.                 }
  129.             }
  130.         }
  131.         //izquierda
  132.         if(columna-1 > 0 && id_Solucion < max)
  133.         {
  134.             if(!lab[fila][columna-1].getRecorrida() && lab[fila][columna-1].getTipo()!='#')
  135.             {
  136.                 solucion[id_Solucion][y_Sol]=lab[fila][columna];
  137.                 encontrado=solucionar(lab[fila][columna-1],fin,fila,columna-1,y_Sol+1);
  138.                 if(encontrado)
  139.                 {
  140.                     if(id_Solucion < max-1)
  141.                     {
  142.                         int i=0;
  143.                         while(solucion[id_Solucion-1][i] != null )
  144.                         {
  145.                             solucion[id_Solucion][i]=solucion[id_Solucion-1][i];
  146.                             i++;
  147.                         }
  148.                     }
  149.                     encontrado=false;
  150.                 }
  151.                 else
  152.                 {
  153.                     solucion[id_Solucion][y_Sol+1]=null;
  154.                     lab[fila][columna-1].setRecorrida(false);
  155.                 }
  156.             }
  157.         }
  158.         lab[fila][columna].setRecorrida(false);
  159.         return false;
  160.     }
  161. }
  162.  
  163.  
 
Omito los metodos para los atributos privados ya saben caules son..........funciono bien con los caso prueba que utilice espero sirva de ejemplo para otros ;)
  
 :good: