¿ Camino mas corto en un Laberinto ?

[kurtjavier]

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

Mostrar/Ocultar Número de línea | Expandir/Contraer | Seleccionar todo

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.  

Clase Laberinto

Mostrar/Ocultar Número de línea | Expandir/Contraer | Seleccionar todo

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.  

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......

[fjmc22]

haber si te sirve este ejemplo que tenia hecho de un ejercicio de backtraking

Mostrar/Ocultar Número de línea | Expandir/Contraer | Seleccionar todo

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.  

[nacheteibo]

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

[kurtjavier]

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.

Mostrar/Ocultar Número de línea | Expandir/Contraer | Seleccionar todo

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.  

 
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: