太爽了，ac了，编了个双向广搜，还挺费劲。还好时间很快。^_^

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

跑了将近45秒！！！

预处理+康托+逆康托的BFS

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

时间主要搭在逆康托上了..

有什么不用逆康托的方法或者更好的Hash么?

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

被Dragon测了一下直接30s.....

两点注意：开始8种目标状态同时进队一次BFS即可；一定预处理再读入

who can tell me ? IF YOU CAN TELL ME ,I WILL THANK YOU VARY MUCH!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

羞辱你们!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

暴力开了8位HASH写BFS居然过了- -

程序写得小丑了- -感觉很慢....

建议不要另建函数..可以用检索树判重.

如下.

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

point=^find;

find=array[1..9]of point;

function h(x:arr):boolean;

var p:point;

begin

p:=@hash;

for i:=1 to 9 do

begin

if i=9 then break;

if (p^[x[i]]=nil) then

begin

new(p^[x[i]]);

p:=p^[x[i]];

fillchar(p^,sizeof(p^),0);

end

else

begin

if p^[x[i]]=nil then new(p^[x[i]]);

p:=p^[x[i]];

end;

end;

if p^[x[i]]=nil then begin new(p^[x[i]]); exit(true); end else exit(false);

end;

状态扩展可用楼下的方法..u:array[1..12]of integer=(1,2,4,5,7,8,1,2,3,4,5,6);

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

b:=q[head];

　　for i:=1 to 12 do

　　begin

　　 x:=b;t:=x[u[i]];x[u[i]]:=x[v[i]];x[v[i]]:=t;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1029;

const

aim: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));

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

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

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

type

matrix=array[1..9]of integer;

var

a,b,x:matrix;

used:array[1..362880]of boolean;

q:array[1..362880]of matrix;

step:array[1..362880]of integer;

head,tail,ans,lim,hh:longint;

i,j,z,t:integer;

f,found:boolean;

function hash(x:matrix):longint;

var

i,j,k:longint;

aaa:array[1..9]of boolean;

begin

fillchar(aaa,sizeof(aaa),false);

hash:=1;

for i:=9 downto 2 do

begin

k:=0;

for j:=1 to x[i]-1 do if not aaa[j] then inc(k);

aaa[x[i]]:=true;

inc(hash,k*product);

end;

end;

begin

head:=0;tail:=8;

for i:=1 to 8 do q[i]:=aim[i];

while headlim then

begin lim:=tail;inc(ans);end;

b:=q[head];

for i:=1 to 12 do

begin

x:=b;t:=x[u[i]];x[u[i]]:=x[v[i]];x[v[i]]:=t;

hh:=hash(x);

if not used[hh] then

begin

step[hh]:=ans;

used[hh]:=true;

inc(tail);

q[tail]:=x;

end;

end;

end;

for z:=1 to 50 do

begin

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

writeln(step[hash(a)]);

end;

end.

8个合法状态BFS，hash函数是：确定key在9的全排列中的第几个位置

用了康托展开暴力上。。19S。。。5555~~~~

写得太丑了。。

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

node=record

z:arr;

step:longint;

num:longint;

end;

const maxn=200000;

n=9;

pre:Array[1..8]of arr=( (6,1,8,7,5,3,2,9,4), //最终的目标状

(8,3,4,1,5,9,6,7,2), //态，很懒直接

(4,9,2,3,5,7,8,1,6), //手输入了。

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

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

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

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

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

go:Array[1..12,0..1]of longint=( (1,4),(2,5),(3,6),(4,7),(5,8),(6,9),(1,2),(4,5),(7,8),(2,3),(5,6),(8,9) ); //移动的方向

var qu:Array[0..maxn]of node;

vis:Array[0..maxn*3]of Boolean;

low:Array[0..maxn*3]of longint;

frac:Array[0..8]of longint;

i,j,k,m,t,l,r,b,f:longint;

s:arr;

sn,lin:node;

c:char;

function Cantor_get_num(var g:arr):longint; //康托展开

var hash:Array[1..n]of Boolean;

i,j,k,p,s,e:longint;

begin

s:=0;

fillchar(hash,sizeof(hash),false);

i:=n;

while i>=1 do begin

E:=i; //不知道为什么到了后面有个状态的时候I突然变得暴大。。于是就这样 处理了

k:=g[i];

hash[k]:=true;

p:=k;

for j:=1 to k-1 do

if hash[j] then dec(p);

i:=E;

inc(s,p*frac);

dec(i);

end;

Cantor_get_num:=s;

end;

function Cantor_get_arr(num:longint):arr; //所谓的逆康托？这题

var hash:Array[1..n]of Boolean; //用不上，我只是熟悉一下

i,j,k,p:longint;

s:arr;

begin

for i:=n downto 1 do begin

k:=num div frac;

num:=num - k*frac;

p:=k;

for j:=1 to k do

if hash[j] then inc(p);

s[i]:=p+1;

end;

Cantor_get_arr:=s;

end;

procedure gin(var x:node); //这两个BFS

begin

inc(f);

vis[x.num]:=true;

if f>maxn then f:=1;

qu[f]:=x;

end;

function gout:node;

begin

inc(b);

if b>maxn then b:=1;

gout:=qu;

vis[qu.num]:=false;

end;

procedure swap(var x,y:integer); //移动用的

var tmp:integer;

begin

tmp:=x; x:=y; y:=tmp;

end;

procedure compare(var g:node); //判断这个状态是否更优

var i,j,k:longint;

begin

if (g.step

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

谁可以把我的程序优化一下。。

···！！竟然要18S.。

超级郁闷，，不过每个数据50组也是·

广搜+HASH+康托+逆康托！！

猛啊！

ipip2005

请读清楚题目拉！！

但不能

7 8 9

5 2 3 （1与5交换）

4 1 6

是不能！

不能啊！！``

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

18S,.

人生中的第一次....

哈哈 我一共跑了30秒

从8个合法状态倒BFS就行了 5秒时限不用是浪费。另：HASH函数可用康托展开

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

主代码：

function news(x:longint):boolean;

var

i:longint;

begin

i:=x mod max;

while (f[i]x) and (f[i]-1) do i:=(i+1) mod max;

if f[i]=x then news:=false

else begin

news:=true;

f[i]:=x;

end;

end;

function judge(s:string):boolean;

var

i:longint;

z,k:array [0..9] of integer;

begin

judge:=true;

for i:=1 to 9 do z[i]:=ord(s[i])-ord('0');

k[1]:=z[1]+z[2]+z[3];

k[2]:=z[4]+z[5]+z[6];

k[3]:=z[7]+z[8]+z[9];

k[4]:=z[1]+z[4]+z[7];

k[5]:=z[2]+z[5]+z[8];

k[6]:=z[3]+z[6]+z[9];

k[7]:=z[1]+z[5]+z[9];

k[8]:=z[3]+z[5]+z[7];

for i:=1 to 8 do if k[i]15 then begin

judge:=false;

exit;

end;

end;

procedure expand(x,y:longint);

var

p:string;

q:char;

k:longint;

begin

if bo then exit;

p:=pre;

q:=p[x];

p[x]:=p[y];

p[y]:=q;

val(p,k);

if news(k) then

if judge(p) then begin

ans[i]:=step[h]+1;

bo:=true;

end

else begin

inc(t);

z[t]:=k;

step[t]:=step[h]+1;

end;

end;

while (h

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我的单广加hash速度还可以，比预想的要快

注意：有8个状态对应同一个标号，我一开始忽略了对称后的4种状态。

ps:为什么我用while not eof do 是答案输出比标准输出长，用for i:=1 to 50 do就AC了？我有点想bs一下vj了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

请问这题如何建立 HASH?