El rompecabezas trata de ir deslizando pieza a pieza, teniendo un hueco vacío ('0').
Asi es como comenta
ivancea96Hola aca esta el codigo para que me aconsegen
saludos y gracias por responder
#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include<queue>
#include <cstdlib>
using namespace std;
class Nodo
{
public:
int profundidad, est;
string str;
Nodo (string str1, int profundidad1, int est1)
{
str = str1; //Estado
profundidad = profundidad1; //Profundidad
est = est1; // valor de evaluacion
}
};
class Profundidad
{
public:
int profundida, est;
string prev;
Profundidad(string prev1, int profundida1, int est1)
{
prev = prev1; //Estado anterior
profundida = profundida1; //Profundidad
est = est1; //Valor de evaluacion
}
};
bool operator< (Nodo n1, Nodo n2)
{
bool sw = true;
if(n1.est == n2.est)
sw = (n1.str < n2.str) ? true:false;
else
sw = (n1.est > n2.est) ? true:false;
return sw;
}
//Evaluacion del nodo
//profundidad
//str: estada
//Meta: estado objetivo
int estimacion(int profundida, string str, string meta)
{
int i1, i2, i3, i4, k1, k2, pi = profundida, ws;
char cg[3][3], cn[3][3];
for (i1 =0; i1<9; i1++)
{
k1 = i1/3;
k2 = i1 - 3 * k1;
cg[k1][k2] = meta.at(i1) - '0';
}
for(i1 =0; i1 < 9; i1++)
{
k1 = i1 /3;
k2 = i1 -3 * k1;
cn[k1][k2] = str.at(i1) - '0';
}
for(i1 =0; i1 < 3; i1++)
{
for(i2 =0; i2 < 3; i2++)
{
ws = 1;
for(i3 =0; i3 < 3 && ws > 0; i3++)
{
for(i4 =0; i4 < 3 && ws >0; i4++)
{
if(cg[i3][i4] == cn[i1][i2])
{
ws = 0;
pi += (abs(i3-i1) + abs(i4-i2));
}
}
}
}
}
if (cn[1][1] != '0')
pi++;
if (cn[0][1] != (cn[0][0]+1)%9)
pi +=2;
if (cn[0][2] != (cn[0][1]+1)%9)
pi +=2;
if (cn[1][2] != (cn[0][2]+1)%9)
pi +=2;
if (cn[2][2] != (cn[1][2]+1)%9)
pi +=2;
if (cn[2][1] != (cn[2][2]+1)%9)
pi +=2;
if (cn[2][0] != (cn[2][1]+1)%9)
pi +=2;
if (cn[1][0] != (cn[2][0]+1)%9)
pi +=2;
if (cn[0][0] != (cn[1][0]+1)%9)
pi +=2;
return pi;
}
int mover (string str, string *res)
{
int k, n = 0;
string str1;
k = str.find("0");
switch(k)
{
case 0:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 1:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 2:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 3:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 4:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 5:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 6:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 7:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;
case 8:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
}
return n;
}
//Inicial
// Meta
void intel(string inicio, string meta)
{
int i1, n, nodo1 = 1, nodo2 =0, profundida =1, ct =1, est;
string str, res[4];
priority_queue<Nodo> p;
map<string, Profundidad> m;
map<string, Profundidad>::iterator it;
bool sw;
est = estimacion(profundida, inicio, meta);
m.insert(pair<string, Profundidad>(inicio, Profundidad("", profundida, est)));
p.push(Nodo(inicio, profundida, est));
while (!p.empty())
{
str = p.top().str;
profundida = p.top().profundidad;
nodo2++;
//Objetivos
if(str == meta)
{
ct = profundida;
break;
}
//Si no hay una meta
//A~nadidi a la cola, tienen el mismo status y mover el marco
else
{
p.pop();
n = mover(str, res);
for (i1 =0; i1 < n; i1++)
{
sw = true;
est = estimacion(profundida+1, res[i1], meta);
it = m.find(res[i1]);
if(it != m.end())
{
if(est < ((*it).second).est)
m.erase(it);
else
sw = false;
}
if (sw)
{
m.insert(pair<string, Profundidad>(res[i1], Profundidad(str, profundida+1, est)));
p.push(Nodo(res[i1], profundida+1, est));
nodo1++;
}
}
}
}
//Salida
printf("Implementacion %d %d, Distancia minima %d\n", nodo1, nodo2, ct);
while(str.length()>0)
{
printf("\n %c %c %c\n", str.at(0), str.at(1), str.at(2));
printf(" %c %c %c\n", str.at(3), str.at(4), str.at(5));
printf(" %c %c %c\n", str.at(6), str.at(7), str.at(8));
it = m.find(str);
str = ((*it).second).prev;
}
}
int main(int argc, char** argv)
{
string inicio = "835416270";
printf ("Prueba n1\n");
string meta = "123804765";
intel(meta, inicio);
printf("Ejemplo 2\n");
meta = "216408753";
intel(inicio, meta);
return 0;
}
Mostrar Mensajes
