#include <iostream>
#include <ctime>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int ROW = 3;
const int COL = 3;
const int MAXDISTANCE = 10000; //最大距离
int abs(int a)
{
if (a>0) return a;
else return -a;
}
typedef struct _Node
{
int digit[ROW][COL];
int dist; // 距离
int dep; // 深度
int index; // 索引值
} Node;
Node src, dest;
vector<Node> node_v; // 储存节点 Open表
bool isEqual(int index, int digit[][COL]) //判断节点是否与索引值指向的节点相同
{
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
{
if (node_v[index].digit[i][j] != digit[i][j])
return false;
}
return true;
}
//重写 输出node
ostream& operator<<(ostream& os, Node& node)
{
cout << "-------------"<<endl;
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if(node.digit[i][j] == 0)
cout <<"| "<< " ";
else
os << "| "<<node.digit[i][j] << " ";
}
os <<"|"<< endl;
cout << "-------------"<<endl;
}
// cout << "-------------"<<endl;
return os;
}
void PrintSteps(int index, vector<Node>& rstep_v) //输出步骤 把最短路径给 rstep_v
{
rstep_v.push_back(node_v[index]);
index = node_v[index].index; //上一个索引位置。
while (index != 0)
{
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
}
for (int i = rstep_v.size() - 1; i >= 0; i--)
cout << "Step " << rstep_v.size() - i
<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b) //交换
{
int t;
t = a;
a = b;
b = t;
}
void Assign(Node& node, int index) //获取节点
{
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
}
int GetMinNode() //获取启发值最小的节点
{
int dist = MAXDISTANCE; //距离
int loc; // 最小化节点的位置
for (int i = 0; i < node_v.size(); i++)
{
if (node_v[i].dist == MAXDISTANCE)
continue;
else if ((node_v[i].dist + node_v[i].dep) < dist)
{
loc = i; //寻找到的node_v里面深度加距离最小的坐标（位置）
dist = node_v[i].dist + node_v[i].dep; //计算有没有比它还要小的节点。
}
}
return loc;
}
bool isExpandable(Node& node) //判断是否可扩展 ，判断是否与 node_v[i].digit 相同，不相同则可以扩展
{
for (int i = 0; i < node_v.size(); i++)
{
if (isEqual(i, node.digit))
return false;
}
return true;
}
int Distance(Node& node, int digit[][COL]) //计算距离 新node与目标之间的距离
{
int distance = 0; //距离
bool flag = false;
for(int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
for (int k = 0; k < ROW; k++)
{
for (int l = 0; l < COL; l++)
{
if (node.digit[i][j] == digit[k][l])
{
distance += abs(i - k) + abs(j - l); //当前的数位置要到应该在的位置绝对值和，即为距离
flag = true;
break;
}
else
flag = false;
}
if (flag)
break;
}
return distance;
}
int MinDistance(int a, int b) //二者取小
{
return (a < b ? a : b);
}
void ProcessNode(int index) //展开节点
{
int x, y;
bool flag;
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if (node_v[index].digit[i][j] == 0) //寻找0的位置，
{
x =i;
y = j;
flag = true;
break;
}
else flag = false;
}
if(flag)
break;
}
Node node_up; //上移操作
Assign(node_up, index); //把启发值最小的节点给 node_up
int dist_up = MAXDISTANCE;
if (x > 0) //上移需要x＞0；x=0不能上移
{
Swap(node_up.digit[x][y], node_up.digit[x - 1][y]); //交换x与（x-1）
if (isExpandable(node_up)) //判断是否与 node_v[i].digit 相同，不相同则可以扩展，即判断有没有重复在 node_v[i]里
{
dist_up = Distance(node_up, dest.digit); //上移后的距离
node_up.index = index; //上移后的距离，它的索引深度赋给 node_up，把父索引位置给它。
node_up.dist = dist_up;
node_up.dep = node_v[index].dep + 1; //深度就加一
node_v.push_back(node_up); //添加到node_v
}
}
Node node_down; //下移操作
Assign(node_down, index);
int dist_down = MAXDISTANCE;
if (x < 2)
{
Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);
if (isExpandable(node_down))
{
dist_down = Distance(node_down, dest.digit);
node_down.index = index;
node_down.dist = dist_down;
node_down.dep = node_v[index].dep + 1;
node_v.push_back(node_down);
}
}
Node node_left;//左移操作
Assign(node_left, index);
int dist_left = MAXDISTANCE;
if (y > 0)
{
Swap(node_left.digit[x][y], node_left.digit[x][y - 1]);
if (isExpandable(node_left))
{
dist_left = Distance(node_left, dest.digit);
node_left.index = index;
node_left.dist = dist_left;
node_left.dep = node_v[index].dep + 1;
node_v.push_back(node_left);
}
}
Node node_right; //右移操作
Assign(node_right, index);
int dist_right = MAXDISTANCE;
if (y < 2)
{
Swap(node_right.digit[x][y], node_right.digit[x][y + 1]);
if (isExpandable(node_right))
{
dist_right = Distance(node_right, dest.digit);
node_right.index = index;
node_right.dist = dist_right;
node_right.dep = node_v[index].dep + 1;
node_v.push_back(node_right);
}
}
node_v[index].dist = MAXDISTANCE;
}
int calDe(int a[ROW][COL]) //求数列逆序数和
{
//一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，
//也就是每个数字前面比它大的数字的个数的和，称为这个状态的逆序。
//若两个状态的逆序奇偶性 相同，则有解，否则无解。
int sum = 0;
for(int i = 0; i < ROW*COL; i ++)
{
for(int j = i+1; j < ROW*COL; j ++)
{
int m,n,c,d;
m = i/ROW;
n = i%ROW;
c = j/COL;
d = j%COL;
if(a[c][d] == 0) continue;
if(a[m][n] > a[c][d]) sum ++;
}
}
return sum;
}
void randDigit(int (*start)[COL])
{
vector<int> temp;
cout<<"生成随机的数列：";
for (int i = 0; i < 9; ++i)
{
temp.push_back(i );
}
srand((unsigned long)time(NULL));
random_shuffle(temp.begin(), temp.end());
for(int i = 0,a = 0; i<3; i++)
{
for (int j = 0 ; j< 3; j++,a++)
{
start[i][j] = temp[a];
}
}
for(int i = 0,a = 0; i<3; i++)
{
for (int j = 0 ; j< 3; j++)
{
cout<< start[i][j]<<" ";
}
}
cout<<"\n";
}
int main()
{
int number;
int n ;
while(1)
{
cout<<"请选择数列生成方式：\n1.手动输入 2.随机生成 0.按“0”退出"<<endl;
cin>>n;
if(n == 1)
{
cout << "输入初始状态:(0表示空格)" << endl;
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
{
cin >> number;
src.digit[i][j] = number;
}
break;
}
else if(n==2)
{
randDigit(src.digit);
break;
}
else if(n==0)
{
exit(0);
}
else
{
cout<<"输入有误，重新输入";
}
}
src.index = 0;
src.dep = 1;
cout << "\n目标状态:" << endl;
for (int i = 0,a = 0; i < ROW; i++)
for (int j = 0; j < COL; j++,a++)
{
dest.digit[i][j] = (a+1)%9;
cout <<dest.digit[i][j]<<" " ;
}
if(!(calDe(src.digit)%2 == calDe(dest.digit)%2))
{
cout << "\nunsolvable\n";
return 0;
}
node_v.push_back(src); //把初始节点添加到node_v（open表）
while (1)
{
int loc; //最小化节点的位置
loc = GetMinNode();
if(isEqual(loc, dest.digit)) //判断节点是否与索引值指向的节点相同 是否是最终节点目标
{
vector<Node> rstep_v;
cout << "\n初始状态：" << endl;
cout << src << endl;
PrintSteps(loc, rstep_v); //把最小的位置节点，添加到rstep_v
cout << "成功!" << endl;
break;
}
else //如果不是最终节点就
ProcessNode(loc);
}
// getchar();
return 0;
}
