队列没开够结果wa了n次。。。

这题直接用hash+单向搜就能够过了

Accepted 有效得分：100 有效耗时：0ms

这题其实无须双搜,因为最多的情况只有9!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

就是简单的双广啦~~

通过...

- 数据 01：正确.. 0ms

- 数据 02：正确.. 0ms

- 数据 03：正确.. 0ms

- 数据 04：正确. 0ms

- 数据 05：正确.. 0ms

- 数据 06：正确.. 0ms

- 数据 07：正确.. 0ms

- 数据 08：正确.. 0ms

最牛B的做法，A*+康托展开……总共写了150行，没有悬念的AC

启发函数：每个数字到答案位置的距离+搜索的深度

康托展开：http://baike.baidu.com/view/437641.htm

PS：虽然比较长，但是分成一块一块的过程或函数来写还是比较好写的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 150ms

├ 测试数据 08：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：278ms

1遍AC。。进入优化时间的阶段。。

IDA*不会。。所以写了个BFS＋hash。。

hash用全排列的编码唯一性，直接开一个9！的桶就可以了。。

如果写单项的bfs最好用循环队列，不然要开10^6的数组。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

不用A*，直接宽搜+hash判重，快吧！

我小菜，不会A*

直接宽搜+HASH判重过了

hash:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

检索树

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

弱题

IDA*算法直接过

A*练手题，没有必要为了过题用BFS，个人看法

没A*...

状态压缩成longlong的整数

hash用康托展开...

然后1Y..

检索树..0ms

直接.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

不稀奇 看我的

绝对没有PS过 可以去看记录R671443

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

我的A*比 yours牛好 今天做梦也会笑……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：164ms

大家用A*吧。

可以过。。

判重优化处理下就好了。先压一下、再拿个used映射就对咯~

晕 慢了NO.2

Accepted

状态 耗时 内存占用

#1 Accepted 93ms 29.613MiB
#2 Accepted 187ms 24.137MiB
#3 Accepted 125ms 29.727MiB
#4 Accepted 125ms 29.621MiB
#5 Accepted 109ms 29.637MiB
#6 Accepted 203ms 24.137MiB
#7 Accepted 171ms 24.137MiB
#8 Accepted 171ms 24.188MiB

import java.util.Scanner;

public class Main
{
static int[][] ans = new int[3][3];
static int best = 100000000;

public static void search(int[][] a, int step, int zerox, int zeroy, int pre)
{
if (step>20)
return;

int i,j;
boolean flag = true;
if (step >= best)
return;
for (i=0;i<3;i++)
for (j=0;j<3;j++)
if (a[i][j] != ans[i][j])
flag = false;
if (flag == true)
{
best = step;
return;
}
if (zerox > 0 && pre != 2)
{
a[zerox][zeroy] = a[zerox-1][zeroy];
a[zerox-1][zeroy] = 0;
search(a, step+1, zerox-1, zeroy, 1);
a[zerox-1][zeroy] = a[zerox][zeroy];
a[zerox][zeroy] = 0;
}
if (zerox < 2 && pre != 1)
{
a[zerox][zeroy] = a[zerox+1][zeroy];
a[zerox+1][zeroy] = 0;
search(a, step+1, zerox+1, zeroy, 2);
a[zerox+1][zeroy] = a[zerox][zeroy];
a[zerox][zeroy] = 0;
}
if (zeroy > 0 && pre != 4)
{
a[zerox][zeroy] = a[zerox][zeroy-1];
a[zerox][zeroy-1] = 0;
search(a, step+1, zerox, zeroy-1, 3);
a[zerox][zeroy-1] = a[zerox][zeroy];
a[zerox][zeroy] = 0;
}
if (zeroy < 2 && pre != 3)
{
a[zerox][zeroy] = a[zerox][zeroy+1];
a[zerox][zeroy+1] = 0;
search(a, step+1, zerox, zeroy+1, 4);
a[zerox][zeroy+1] = a[zerox][zeroy];
a[zerox][zeroy] = 0;
}
}

public static void main(String args[])
{
int[][] init =
{
{1,2,3},
{8,0,4},
{7,6,5}
};
Scanner in =new Scanner(System.in);
String s = in.nextLine();
int index = 0;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
{
ans[i][j] = s.charAt(index)-'0';
index++;
}
search(init, 0, 1, 1, 0);
System.out.println(best);
}
}

39行AC
#include<cstdio>
#include<cstdlib>
#include<cstring>
char a[4000000][10];
int dj[1000000],bj1[1000000],pd1[9][9][9][9][9][9][9][9],head=0,tail=1,j;
void bfs() {
do {
head++;
for(int i=1; i<=4; i++) {
j=bj1[head]+2*i-5;
if(2*i-5==-1 &&(bj1[head]==3 || bj1[head]==6)) continue;
if(2*i-5==1 &&(bj1[head]==2 || bj1[head]==5)) continue;
if(j>=0&&j<9) {
strcpy(a[++tail],a[head]);
a[tail][bj1[head]]=a[tail][j];
a[tail][j]='0';
if(pd1[a[tail][0]-48][a[tail][1]-48][a[tail][2]-48][a[tail][3]-48][a[tail][4]-48][a[tail][5]-48][a[tail][6]-48][a[tail][7]-48]==0) {
pd1[a[tail][0]-48][a[tail][1]-48][a[tail][2]-48][a[tail][3]-48][a[tail][4]-48][a[tail][5]-48][a[tail][6]-48][a[tail][7]-48]=1;
dj[tail]=dj[head]+1;
bj1[tail]=j;
} else
tail--;
if(!strcmp(a[tail],"123804765")) {
printf("%d",dj[tail]);
exit(0);
}
}
}
} while(head<tail);
}
int main() {
gets(a[1]);
for(int jji=0; jji<9; jji++) {
if(a[1][jji]=='0') {
bj1[1]=jji;
bfs();
}
}
}