/**
* ejemplo backtracking
* laberinto del raton y el queso
*
* @LuisTapia
* @4/4/2019
*/
public class RatonQueso
{ private static int R = 3;
private static int Q = 5;
private static int L = 0;
private static int V = 2;
private int xRaton,yRaton,xQueso,yQueso;
private int [][] mapa;
private int v = Integer.MAX_VALUE;
private String mejor;
private int soluciones = 0;
public static void main(String arg[])
{ int [][] mapa1 = new int[][] {{1,0,1,1,0,0,0},
{0,0,1,0,0,1,0},
{0,0,1,0,1,1,0},
{0,0,0,0,1,0,0},
{0,0,0,0,0,0,0}};
int [][] mapa2 = new int[][] {{1,0,1,1,0,0,0},
{0,0,1,0,0,1,0},
{0,0,1,0,1,1,0},
{0,0,0,0,1,0,0},
{0,0,0,0,0,0,0}};
//int xr = 2,yr = 4;
//int xq = 6,yq = 2;
int xr = 1,yr = 1,xq = 5,yq = 3;
RatonQueso ratonQueso1 = new RatonQueso(mapa1,xr,yr,xq,yq);
String res;
[Link]("Laberinto:");
[Link]( [Link]());
[Link]("Primera solucion:");
res = "No hay Camino";
if([Link](xr,yr))
res = [Link]();
[Link](res);
RatonQueso ratonQueso2 = new RatonQueso(mapa2,xr,yr,xq,yq);
[Link]("////////////////////////////");
[Link]("Mejor solucion:");
res = "No hay Camino";
if([Link](xr,yr,0)<Integer.MAX_VALUE)
res = [Link]();
[Link]("////////////////////////////");
[Link](res);
}
public RatonQueso(int[][] mapa, int xR,int yR,int xQ,int yQ)
{ [Link] = mapa;
/*xRaton = xR-1;
yRaton = [Link] - yR;
xQueso = xQ-1;
yQueso = [Link] - yQ;*/
xRaton = xR;
yRaton = yR;
xQueso = xQ;
yQueso = yQ;
}
public boolean encontrar(int xR,int yR)
{ boolean seEncuentra = esSolucion(xR,yR);
if(seEncuentra)
mapa[yR][xR] = V;
else if(!seEncuentra && esLibre(xR,yR))
{ int p= 0;
mapa[yR][xR] = V;
p = encontrar(xR, yR-1) ? p+1: p;
p = encontrar(xR+1,yR) ? p+1: p;
p = encontrar(xR, yR+1) ? p+1: p;
p = encontrar(xR-1,yR) ? p+1: p;
if(sinSolucion(p))//p = 0 soluciones
mapa[yR][xR] = L;
else seEncuentra = true;
}
return seEncuentra;
}
public boolean esSolucion(int xR,int yR)
{ return xR == xQueso && yR == yQueso;
}
public boolean esLibre(int xR,int yR)
{ return xR>=0 && xR<mapa[0].length && yR>=0 && yR<[Link]
&& mapa[yR][xR] == L;
}
public boolean sinSolucion(int p)
{ return p == 0;
}
public String mapaToString()
{ return toStringDesde(0,0);
}
public String mejorMapaToString()
{ return mejor;
}
public int encontrarMejor(int xR,int yR,int vis)
{ int p = 0;
if(esLibre(xR,yR))
{ mapa [yR][xR] = V;
if(esSolucion(xR,yR))
{ String unaSolucion = mapaToString();
soluciones++;
if(vis<v)
{ v = vis;//v es infinito la primera vez
mejor = unaSolucion;
[Link]("\t\t**mejor**");
}
[Link]("\t\t Solucion "+soluciones);
[Link](unaSolucion);
}
else
{ p += [Link]([Link](encontrarMejor(xR ,yR-1
,vis+1),
encontrarMejor(xR+1 ,yR
,vis+1)),
[Link](encontrarMejor(xR ,yR+1
,vis+1),
encontrarMejor(xR-1 ,yR
,vis+1)));
}
mapa[yR][xR] = L;
}
return p;
}
public String toStringDesde(int x,int y)
{
String cad ="";
if(x<mapa[0].length&&y<[Link])
{ /*if(x==xRaton&&y==yRaton) cad+= "R";
else if(x==xQueso&&y==yQueso) cad+= "Q";
else*/ cad += mapa[y][x];
if(x<mapa[0].length-1)
cad += " ";
cad += toStringDesde(x+1,y);
}
else
{ cad += "\n";
if(y<[Link])
cad += toStringDesde(0,y+1);
else
{ cad += "xRaton: "+ xRaton +"\n";
cad += "yRaton: "+ yRaton +"\n";
cad += "xQueso: "+ xQueso +"\n";
cad += "yQueso: "+ yQueso +"\n";
}
}
return cad;
}
