求算法-----百度编程大赛试题----类似九格宫(C++算法实现)
以下是我博客 http://blog.csdn.net/chenyujing1234/article/details/7696535
中的内部，里面给出问题及一种解法，但解法效率低下，想请教大家有没有更好的方法。
===================================================================================================
一、题目
题目是这样的：
八方块移动游戏要求从一个含8个数字(用1-8表示)的方块以及一个空格方块(用0表示)的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其它位置上有3个方向可移动。
例如，假设一个3x3矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所用可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径;在上面的例子中，最短路径为5。如果不存在从初始状态到目标状态的任何路径，则称该组状态无解。
请设计算法找到从八方块的某初始状态到某目标状态的所有可能路径的最短路径，并用C/C++实现。
输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成(0表示空格)，1-8表示8个数字方块)，每行3个数字，数字之间用空格隔开。假定start.txt和goal.txt不会相同。
输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数;如果输入数据无解，输出-1.请在数字输出后在输出一回车换行符。
自测用例：如果输入为：start.txt和goal.txt，则产生的输出应为：
5
如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21
如果用
7 5 2
0 6 3
4 1 8
替换start.txt中的内容，则产生的输出应为：
-1
评分规则：我们将首先使用10组不同的start.txt和goal.txt进行测试，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒(内存使用不限制)，否则该用例不得分;
每个选手的得分由两部分组成：
正确性得分(10秒内能产生正确结果的测试用例数量x10)和时间性能得分(10秒钟内产生这些正确结果的测试用例的平均运行毫秒数)。
正确性得分高的将始终比正确性得分低的排名在前，即使前者的平均运行时间比后者的要长;正确性得分相同的将按平均运行时间的快慢排列。
二、C++算法实现
1、第一种算法：全部遍历，直到找到。
1、1 结论
虽然结果正确，但耗时太长，与评分规则不合。
如上图所求，它采用全部遍历的方法，按顺序交换位置后往vector后面存储。
指针依次向vector后面推进，如果我们的结果出现在vector的尾部，那么运算的时间是相当长的。
1、2 代码实现
#pragma warning(disable:4786)
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
using namespace std;
const int N = 3;// 数组的边长
class CNineWomb
{
public:
CNineWomb(char cInData[N][N])
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
m_cData[i][j] = cInData[i][j];
}
}
m_iMoveCount = 0;
}
bool operator ==(const CNineWomb& inCNineWomb)
{
for(int i = 0;i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(inCNineWomb.m_cData[i][j] != m_cData[i][j])
{
return false;
}
}
}
return true;
}
void CNineWomb_Printf()
{
for(int i = 0;i < N; i++)
{
for(int j = 0;j < N; j++)
{
cout << m_cData[i][j] << " ";
}
cout << endl;
}
}
public:
char m_cData[N][N];
int m_iMoveCount;
};
void main()
{
// 第一组数据 (无解)
//char cStartData[N][N] = { '1', '5', '8', '2', '6', ' ', '4', '7', '3'};
//char cGoalData[N][N] = { '1', '2', '3', '8', ' ', '4', '7', '6', '5'};
// 第二组数据 (无解)
//char cStartData[N][N] = { '1', '2', '3', '8', ' ', '4', '7', '6', '5'};
//char cGoalData[N][N] = { '1', '5', '8', '2', '6', ' ', '4', '7', '3'};
// 第三组数据 (有解)
//char cStartData[N][N] = { '8', ' ', '3', '2', '1', '4', '7', '6', '5'};
//char cGoalData[N][N] = { '1', '2', '3', '8', ' ', '4', '7', '6', '5'};
// 第四组数据 (有解)
char cStartData[N][N] = { '7', '8', '4', '3', '5', '6', '1', ' ', '2'};
char cGoalData[N][N] = { '1', '2', '3', '8', ' ', '4', '7', '6', '5'};
int iMoveCount = 1;// 移动步数
int iSpaceI = 0, iSpaceJ = 0;// 存储空格子所在的位置
vector<CNineWomb> VecCNineWomb;// 存储盘数据的容器
vector<CNineWomb>::iterator itVecCNineWomb;
vector<CNineWomb>::iterator iter; // 临时指针
map <int,int> mapSonFather;// 根据sun的m_iMoveCount找父亲的m_iMoveCount;
// 加载源数据与目标数据
CNineWomb NWStartData(cStartData);
NWStartData.m_iMoveCount = 0;
CNineWomb NWGoalData(cGoalData);
VecCNineWomb.reserve(200000); // 容器中预留200000个空间
VecCNineWomb.push_back(NWStartData);// 把源数据压到容器中
itVecCNineWomb = VecCNineWomb.begin();
mapSonFather.insert(make_pair(0,0));
while(1)
{
//cout << iMoveCount <<endl;
if(itVecCNineWomb == VecCNineWomb.end())
{
cout << "There is no trace from soure to aim!" << endl;
break;
}
// 拷贝数据
CNineWomb NWFather((*itVecCNineWomb).m_cData);
NWFather.m_iMoveCount = (*itVecCNineWomb).m_iMoveCount;
// 是否是目标,是则退出
if(NWFather == NWGoalData)
break;
// 找出空格位置
iSpaceI = 0, iSpaceJ = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(' ' == NWFather.m_cData[i][j])
{
iSpaceI = i;
iSpaceJ = j;
break;
}
}
}
// 往上移
if(N-1 > iSpaceI)
{
CNineWomb NWSunUp(NWFather.m_cData);
swap(NWSunUp.m_cData[iSpaceI+1][iSpaceJ], NWSunUp.m_cData[iSpaceI][iSpaceJ]);
// 如果sun为全新的节点，将sun插入VecCNineWomb表.
if((iter = find(VecCNineWomb.begin(), VecCNineWomb.end(), NWSunUp)) == VecCNineWomb.end())
{
NWSunUp.m_iMoveCount = iMoveCount;
mapSonFather.insert(make_pair(NWSunUp.m_iMoveCount, NWFather.m_iMoveCount));
iMoveCount++;
VecCNineWomb.push_back(NWSunUp);
// 是否是目标,是则退出
if(NWSunUp == NWGoalData)
{
itVecCNineWomb = VecCNineWomb.end() - 1;
break;
}
}
}
// 往下移
if(0< iSpaceI)
{
CNineWomb NWSunDown(NWFather.m_cData);
swap(NWSunDown.m_cData[iSpaceI-1][iSpaceJ], NWSunDown.m_cData[iSpaceI][iSpaceJ]);
if((iter = find(VecCNineWomb.begin(), VecCNineWomb.end(),NWSunDown)) == VecCNineWomb.end())
{
NWSunDown.m_iMoveCount = iMoveCount;
mapSonFather.insert(make_pair(NWSunDown.m_iMoveCount, NWFather.m_iMoveCount));
iMoveCount++;
VecCNineWomb.push_back(NWSunDown);
// 是否是目标,是则退出
if(NWSunDown == NWGoalData)
{
itVecCNineWomb = VecCNineWomb.end() - 1;
break;
}
}
}
// 往左移
if(N-1 > iSpaceJ)
{
CNineWomb NWSunLeft(NWFather.m_cData);
swap(NWSunLeft.m_cData[iSpaceI][iSpaceJ+1], NWSunLeft.m_cData[iSpaceI][iSpaceJ]);
if((iter = find(VecCNineWomb.begin(), VecCNineWomb.end(), NWSunLeft)) == VecCNineWomb.end())
{
NWSunLeft.m_iMoveCount = iMoveCount;
mapSonFather.insert(make_pair(NWSunLeft.m_iMoveCount, NWFather.m_iMoveCount));
iMoveCount++;
VecCNineWomb.push_back(NWSunLeft);
// 是否是目标,是则退出
if(NWSunLeft == NWGoalData)
{
itVecCNineWomb = VecCNineWomb.end() - 1;
break;
}
}
}
// 往右移
if(0 < iSpaceJ)
{
CNineWomb NWSunRight(NWFather.m_cData);
swap(NWSunRight.m_cData[iSpaceI][iSpaceJ-1], NWSunRight.m_cData[iSpaceI][iSpaceJ]);
if((iter = find(VecCNineWomb.begin(), VecCNineWomb.end(), NWSunRight)) == VecCNineWomb.end())
{
NWSunRight.m_iMoveCount = iMoveCount;
mapSonFather.insert(make_pair(NWSunRight.m_iMoveCount, NWFather.m_iMoveCount));
iMoveCount++;
VecCNineWomb.push_back(NWSunRight);
// 是否是目标,是则退出
if(NWSunRight == NWGoalData)
{
itVecCNineWomb = VecCNineWomb.end() - 1;
break;
}
}
}
itVecCNineWomb++;
}// end of while(1)
cout << iMoveCount << endl;
if(itVecCNineWomb != VecCNineWomb.end())// 找到路径
{
// 把与目标相匹配的CNineWomb取出来
CNineWomb NWSunMatch((*(itVecCNineWomb)).m_cData);
NWSunMatch.m_iMoveCount = (*(itVecCNineWomb)).m_iMoveCount;
int x = NWSunMatch.m_iMoveCount;
int iIndex = 0;
cout << "NWSunMached:" << endl;
NWSunMatch.CNineWomb_Printf();
// 打印出过程
cout << "Process:" << endl;
while(0 != x)
{
iter = VecCNineWomb.begin();
while(iter != VecCNineWomb.end())
{
if((*iter).m_iMoveCount == mapSonFather[x])
break;
else
iter++;
}
CNineWomb sun((*iter).m_cData);
sun.m_iMoveCount = (*iter).m_iMoveCount;
x = sun.m_iMoveCount;
cout << "========================"<< iIndex++ << "=============================" << endl;
sun.CNineWomb_Printf();
}
}
else// 打印所有的接点。
{
cout << "=====================================================" << "sorry! no found" << endl;
}
system("pause");
return ;
}
[解决办法]
谁说的，我就是普通广度搜索，完全可以
