wsj

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 2025ms

├ 测试数据 10：答案正确... 2088ms

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

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

我终于明白了。。。。。。原来所谓的反向搜不用搜8次，只用把8个状态压进队列，然后搜一次就行了。。。。。。

个人认为还是反搜比较好，不超时

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 1632ms

├ 测试数据 10：答案正确... 1538ms

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

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

正向BFS+九进制hash+目标状态打表....

---|---|---|以下是鄙人猥琐的代码---|---|---|program vijos1029;type node=array[0..9] of longint;var start:node; i,j,head,tail:longint; queue:array[1..370000] of node; target:array[1..8] of longint; hash:array[672604..42374116] of boolean;function ok(status:node):boolean;var s:longint;begin s:=status[1]*4782969+status[2]*531441+status[3]*59049+status[4]*6561+status[5]*729+status[6]*81+status[7]*9+status[8]; if (s=target[1]) or (s=target[2]) or (s=target[3]) or (s=target[4]) or (s=target[5]) or (s=target[6]) or (s=target[7]) or (s=target[8]) then ok:=true else ok:=false;end;procedure bfs;var t:longint; x:node; flag:boolean;begin if ok(queue[1]) then begin writeln(0); exit; end; flag:=true; while (head

wa了5次...

用康托展开+宽搜......不要开30W的字符串数组....

还有

"

但不能

7 8 9

5 2 3 （1与5交换）

4 1 6

"

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 509ms

├ 测试数据 10：答案正确... 416ms

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

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

双向广搜就是强、、、

虽然wa了6次，但是每次都有体会。。特别最后AC了这道第一次广搜。。真是眼泪都流出来了。。一个下午。。学了广搜.。学了坚韧。。。

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 3400ms

├ 测试数据 10：答案正确... 2994ms

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

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

常用BFS+(hash+康托展开):

判断结果时死方法，所以时间比较长，建议把目标状态打表！

const int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};

int Key(int b)

{

int total = 0;

int a[9];

int temp, i, j, k = 0;

for (i = 0; i < 3; i++)

for (j = 0; j < 3; j++)

a[k++] = board.B[i][j];

for (i = 0; i < 8; i++)

{

temp = 0;

for (j = i+1; j < 9; j++)

if (a[j] < a[i]) temp++;

total += temp*fac[8-i];

}

return total;

}

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

1A..可惜做得久了点.时间慢了点...

其实还肯打个表...

我的程序就是先打个表,然后再边读边输出.

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

话说我交的时候.Sunny运行我的程序时,vj突然挂了大概半分钟左右.

我想是不是我的程序弄的呢.

于是我又用小号交了下...

vj没挂,却我只给80分...有两个点超时...

话说我的程序是先求出所有结果后,再读入输出的.

按理说应该每个点耗时一样啊...最快的点与最慢的竟然差2S!

Sunny稳定性值得怀疑...

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 1603ms

├ 测试数据 10：答案正确... 1634ms

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

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

时间好囧......膜拜xjcjason....编程复杂度很低的说.......

那个 Const 值得学习~~~~

8个最终状态一起放进去反向bfs一遍就好了

program vijos1029SEARCH;

type stype=array[1..9] of integer;

const goal:array[1..8]of stype=((2,7,6,9,5,1,4,3,8)

,(2,9,4,7,5,3,6,1,8),(4,3,8,9,5,1,2,7,6),(4,9,2,3,5,7,8,1,6)

,(6,1,8,7,5,3,2,9,4)

,(6,7,2,1,5,9,8,3,4)

,(8,1,6,3,5,7,4,9,2)

,(8,3,4,1,5,9,6,7,2));

fac:array[0..9] of longint=(1,1,2,6,24,120,720,5040,40320,362880);

mov:array[1..12,1..2] of integer=((1,2),(1,4),(2,3),(2,5),(3,6),(4,5),(4,7),(5,6),(5,8),(6,9),(7,8),(8,9));

var v:array[0..362879] of integer;i,j,op,tt,clo,k:longint;

da:array[1..364000] of stype;can:array[1..364000] of longint;

a:array[1..50] of longint; tmp,newe:stype;

function cantor(a:stype):longint;

var sum,i,tmp:longint;

begin

sum:=0;

for i:=1 to 8 do

begin

tmp:=0;

for j:=i+1 to 9 do

if a[i]>a[j] then inc(tmp);

sum:=sum+tmp*fac[9-i];

end;

exit(sum);

end;

begin

op:=0;

for i:=0 to 362879 do v[i]:=-1;

for i:=1 to 50 do

begin

for j:=1 to 9 do

read(tmp[j]);

a[i]:=cantor(tmp);

end;

for clo:=1 to 8 do

begin

da[clo]:=goal[clo];

can[clo]:=cantor(da[clo]);

v[can[clo]]:=0;

end;

repeat

inc(op);

for i:=1 to 12 do

begin

move(da[op],newe,18);

tt:=newe[mov];newe[mov]:=newe[mov];newe[mov]:=tt;

k:=cantor(newe);

if (v[k]=-1) then begin

inc(clo);

v[k]:=v[can[op]]+1; can[clo]:=k;

move(newe,da[clo],18);

end;

end;

until (clo>=362880);

for i:=1 to 50 do

begin

{ if v[a[i]]=0 then writeln('-1')

else} writeln(v[a[i]]);

end;

end.

反向搜索TLE，正向AC

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 2291ms

├ 测试数据 10：答案正确... 1947ms

ORZ Jason911

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 1806ms

├ 测试数据 10：答案正确... 1791ms

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

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

评测机太NB了 在自家电脑上8秒出结果的程序只要1.8秒就能出结果。。

反向广搜+hash

虽然目标状态有8种,逐一搜索会非常费时.

不过由都是由旋转得来的.

所以只要先预处理搜索任意种的答案.

每次把读入的数据进行8种旋转,输出最小的那个即可.

感谢mick的提示

不过mick写出来的也比我快太多了吧..

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 1619ms

├ 测试数据 10：答案正确... 1634ms

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

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

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 2916ms

├ 测试数据 10：答案正确... 2494ms

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

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

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 3728ms

├ 测试数据 10：答案正确... 3181ms

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

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

单向广搜+康托展开，过的太险了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我用双向宽度搜索!!!!

哈哈!!

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 2947ms

├ 测试数据 10：答案正确... 2650ms

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

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

为什么我没超时呢？？？？？？ 附程序

#include

struct{

int a[10],step;

}line[400000];

int a[10],done[400000];

int jc[10]={0,1,2,6,24,120,720,5040,40320,362880};

int ans[10]={69075,77577,135290,157121,205760,227591,285304,293806};

int suan(int a[10]){

int i,j,k=8,l,s=1;

for(i=1;i

欢迎到我的博客看看：

hi.baidu.com/wx405557858

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 1494ms

├ 测试数据 10：答案正确... 1525ms

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

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

const bigprime=3214567;

fac:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);

change:array[1..2,1..12]of integer=((1,1,2,2,3,4,4,5,5,6,7,8),

(2,4,3,5,6,5,7,6,8,9,8,9));

w:array[1..8,1..9]of integer=((2,7,6,9,5,1,4,3,8)

,(2,9,4,7,5,3,6,1,8)

,(4,3,8,9,5,1,2,7,6)

,(4,9,2,3,5,7,8,1,6)

,(6,1,8,7,5,3,2,9,4)

,(6,7,2,1,5,9,8,3,4)

,(8,1,6,3,5,7,4,9,2)

,(8,3,4,1,5,9,6,7,2));

type arr=array[1..9]of integer;

point=^rec;

rec=record

v:arr;

step:integer;

next:point;

end;

var hash:array[0..bigprime-1]of point;

q:array[0..400000]of rec;

a:arr;

i,j,sum:integer;

key:longint;

now:point;

flag:boolean;

function equal(a,b:arr):boolean;

var i:integer;

begin

for i:=1 to 9 do if a[i]b[i] then exit(false);

exit(true);

end;

function update(a:arr;p,q:integer):arr;

begin

update:=a;

update[p]:=a[q];

update[q]:=a[p];

end;

function find(a:arr;step:integer):boolean;

var now:point;

i:integer;

key:longint;

begin

key:=0;

for i:=1 to 8 do key:=(key+(a[i]-1)*fac[i]) mod bigprime;

now:=hash[key mod bigprime];

while nowNIL do

begin

if equal(now^.v,a)

then begin

if step=r;

end;

begin

bfs;

for sum:=1 to 50 do

begin

for j:=1 to 9 do read(a[j]);

key:=0;

for i:=1 to 8 do key:=(key+(a[i]-1)*fac[i]) mod bigprime;

now:=hash[key];

flag:=true;

while nowNIL do

begin

if equal(now^.v,a)

then begin writeln(now^.step); flag:=false; break; end;

now:=now^.next;

end;

if flag then writeln(-1);

readln;

end;

end.

bfs+康托hash判重,还是反搜好~~

貌似耗时还是好多。代码好长。