百行的程序照样AC此题，具体解析见：

http://www.rqnoj.cn/Solution_Show.asp?DID=3170

状态题目:八数码难题

题目编号:70-八数码难题 查看该题

状态: Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2008-11-2 16:29:00

有效耗时： 2297毫秒

测试结果1: 通过本测试点|有效耗时203:ms

测试结果2: 通过本测试点|有效耗时187:ms

测试结果3: 通过本测试点|有效耗时187:ms

测试结果4: 通过本测试点|有效耗时250:ms

测试结果5: 通过本测试点|有效耗时250:ms

测试结果6: 通过本测试点|有效耗时266:ms

测试结果7: 通过本测试点|有效耗时250:ms

测试结果8: 通过本测试点|有效耗时266:ms

测试结果9: 通过本测试点|有效耗时250:ms

测试结果10: 通过本测试点|有效耗时188:ms

这道题本来就可以不用A*的……

9494

八数码问题不就是学广度优先搜索的入门例题吗？

要用什么启发式搜索啊！

我用你的算法变得但总是无法AC。提示是超时。这是怎么回事啊？

#include<iostream>

#include<string>

#include<vector>

#include<fstream>

#include<stdlib.h>

#include<cstdlib>

using namespace std;

struct map_node

{

string s;

long step;

map_node ( string x )

{

s = x;

step = 0;

}

map_node ()

{

s = " ";

step = 0;

}

};

struct flag_node

{

bool f;

string s;

flag_node ( string x )

{

s = x;

f = false;

}

flag_node ()

{

s = " ";

f = false;

}

};

const string aim = "123804765";

const string aim2 = "123804765";

int moves[4] = { 1 , -1 , 3 , -3 };

const long maxn = 1200007;

map_node opt[maxn];

flag_node flag[maxn];

bool fuck = false;

long hashing ( string str )

{

long num = atol ( str.c_str() ) % maxn;

return num;

}

void check_done ( map_node str )

{

if ( str.s == aim2 )

{

//cout << str.s << endl << goal << endl;//for testing

cout << str.step << endl;

fuck = true;

exit ( 0 );

}

}

int main()

{

long i , j , x , m;

bool found;

string tempin;

string y;

ifstream fin ( "in.in" );

fin >> tempin;

opt[0].s = tempin;

opt[0].step = 0;

x = hashing ( tempin );

flag[x].f = true;

flag[x].s = tempin;

i = 0;

j = 0;

while ( i <= j )

{

int w = opt[i].s.find ( "0" , 0 );

for ( int k = 0 ; k != 4 ; ++k )

{

if ( fuck )

{

return 0;

}

if ( ( w % 3 == 2 ) && ( k != 0 ) || ( w % 3 == 0 ) && ( k != 1 ) || ( w % 3 == 1 ) )

{

int Newpos = w + moves[k];

if ( Newpos >= 0 && Newpos <= 8 )

{

y = opt[i].s;

swap ( y[w] , y[Newpos] );

//cout << y << endl;//for testing

x = hashing ( y );

found = false;

while ( x < maxn && flag[x].f )

{

if ( flag[x].s == y )

{

//cout << x << endl;//for testing

found = true;

break;

}

++x;

}

if ( !found )

{

++j;

m = j;

opt[m].s = y;

opt[m].step = opt[i].step + 1;

//cout << opt[m].step << endl;//for testing

flag[x].f = true;

flag[x].s = y;

//cout << aim2 << endl;//for testing

check_done ( opt[m] );

}

}

}

}

++i;

}

return 0;

}