讨论 / TLE,怎么搞
cszqwe 2011-08-12 20:00:00
点我顶贴 收藏 删除
program llx;

const maxn=1200007;

c:array[1..4]of longint=(-1,-3,1,3);

goal:string='123804765';

var ss,t,i,j,n,m,k,o,p:longint;

b:array[1..maxn]of longint;

sh:array[1..maxn]of string[9];

pd:boolean;

s:array[1..400000]of string[9];

a:array[1..400000]of longint;

ls:string;

kx:array[1..4]of integer;

function hash(s:string):longint;

var q:int64;

begin

val(s,q);

hash:=q mod maxn;

end;

begin

readln(s[1]);

o:=hash(s[1]);

b[o]:=1;

sh[o]:=s[1];

ss:=1;

a[1]:=0;

t:=1;

repeat

for i:=1 to 4 do kx[i]:=i;

i:=4;

p:=pos('0',s[ss]);

if p=1 then begin kx[1]:=0;kx[2]:=0;end;

if p=2 then kx[2]:=0;

if p=3 then begin kx[2]:=0;kx[3]:=0;end;

if p=4 then kx[1]:=0;

if p=6 then kx[3]:=0;

if p=7 then begin kx[1]:=1;kx[4]:=0;end;

if p=8 then begin kx[3]:=0;end;

if p=9 then begin kx[3]:=0;kx[4]:=0;end;

for i:=1 to 4 do

if kx[i]<>0 then

begin

ls:=s[ss];

ls[p]:=ls[p+c[i]];

ls[p+c[i]]:='0';

o:=hash(ls);

pd:=true;

while (o<maxn)and(b[o]=1) do

begin

if sh[o]=ls then begin pd:=false;break; end;

inc(o);

end;

if (o<=maxn)and pd then

begin

b[o]:=1;

sh[o]:=ls;

inc(t);

a[t]:=a[ss]+1;

s[t]:=ls;

if ls=goal then begin writeln(a[t]);halt;end;

end;

end;

inc(ss);

until ss>t;

end.

单向BFS+HASH,看别人这么写100,我咋TLE了?

#1 594250@2011-08-12 19:39:00
回复 删除
那就用双向嘛
#2 cszqwe@2011-08-12 20:00:00
回复 删除
回复 沙发594250 的帖子

单项可以过的,我的hash可能有问题

查看更多回复
提交回复