https://vjudge.net/problem/UVA-1343
题意：如图所示，一共有8个1,8个2和8个3，如何以最少的移动来使得中间8个格子都为同一个数。
思路：状态空间搜索问题。
用IDA*算法的话会比较快，而且代码比较简洁。
IDA*的关键就是要寻找一个估价函数h（），在这道题目中，每次移动最多只会使一个格子的数字正确，所以当maxd-d<h()时便可以剪枝。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std; int position[][] = {
{ , , , , , , }, { , , , , , , }, //八个方向格子的坐标值
{ , , , , , , }, { , , , , , , },
{, , , , , , }, { , , , , , , },
{, , , , , , }, { , , , , , , }
}; int goal[] = { , , , , , , , }; //目标状态的坐标 int a[];
char order[]; //记录路径 bool is_goal() //判断是否已达到目标状态
{
for (int i = ; i < ; i++)
{
if (a[goal[i]]!=a[goal[i + ]]) return false;
}
return true;
} int h() //算出不匹配的最小值
{
int n1 = , n2 = , n3 = ;
for (int i = ; i < ; i++)
{
if (a[goal[i]] == ) n1++;
else if (a[goal[i]] == ) n2++;
else if (a[goal[i]] == ) n3++;
}
return -max( max(n1, n2),n3);
} void rotate(int k) //往指定的方向移动
{
int temp = a[position[k][]];
for (int i = ; i < ; i++)
{
a[position[k][i-]] = a[position[k][i]];
}
a[position[k][]] = temp;
} bool dfs(int d, int maxd)
{
if (is_goal()) return true;
if (maxd - d < h()) return false; //剪枝
int old[]; //用来保存原来的序列
memcpy(old, a, sizeof(a));
for (int i = ; i < ; i++)
{
rotate(i); //往第i个方向移动
order[d] = i + 'A';
if (dfs(d + , maxd)) return true;
memcpy(a, old, sizeof(old)); //如果失败，则恢复原来序列
}
return false;
} void solve()
{
if (is_goal())
{
cout << "No moves needed" << endl << a[] << endl;
return;
}
for (int maxd = ;; maxd++)
{
if (dfs(, maxd))
{
order[maxd] = '\0';
cout << order << endl << a[] << endl;
return;
}
}
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> a[] && a[])
{
for (int i = ; i < ; i++)
cin >> a[i];
solve();
}
return ;
}