讨论 / 思路
ZH 2012-09-11 22:24:00
点我顶贴 收藏 删除
how to Ac it?
#1 lyc@2010-09-18 03:34:00
回复 删除
采用GD算法
#2 烂笔头@2010-09-23 01:51:00
回复 删除
能否详细点
#3 what?@2010-09-23 06:43:00
回复 删除
某些点只能是某个时间段之后不能走

而所谓安全的地方就永远都不会有危险

所以:var m1,m2:array[-10..500,-10..500] of boolean;

t:array[1..1000,1..1000,1..2] of longint;

b:array[1..1000000,1..2] of longint;

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

m,i,x,y,z,k,p,q,w:longint;

begin

read(m);

for i:=1 to m do

begin

read(x,y,z);

m1[x,y]:=true;

m1[x+1,y]:=true;

m1[x-1,y]:=true;

m1[x,y+1]:=true;

m1[x,y-1]:=true; {M1中 FALSE 表示永远安全的点}

inc(a[z]); {A数组 记录某时刻 共有几颗流星}

t[z,a[z],1]:=x;

t[z,a[z],2]:=y;{T[I,J,K] I:表示某时刻 J:表示他是该时刻的第几颗流星 K:表示横纵坐标}

end;

q:=1;

w:=1;

b[i,1]:=0;

b[i,2]:=0;

repeat

inc(k);

for i:=1 to a[k] do

begin

m2[t[k,i,1],t[k,i,2]]:=true;

m2[t[k,i,1]+1,t[k,i,2]]:=true;

m2[t[k,i,1]-1,t[k,i,2]]:=true;

m2[t[k,i,1],t[k,i,2]+1]:=true;

m2[t[k,i,1],t[k,i,2]-1]:=true;

end; {处理该时间之后不能走的点}

剩下的就是标准BFS 就不废话了

for i:=q to w do

if not m1[b[i,1],b[i,2]] then

begin

write(k-1);

halt;

end

else

begin

if (not m2[b[i,1]-1,b[i,2]])and(b[i,1]-1>=0)

then begin

inc(p);

m2[b[i,1]-1,b[i,2]]:=true;

b[w+p,1]:=b[i,1]-1;

b[w+p,2]:=b[i,2];

end;

if (not m2[b[i,1],b[i,2]-1])and(b[i,2]-1>=0)

then begin

inc(p);

m2[b[i,1],b[i,2]-1]:=true;

b[w+p,1]:=b[i,1];

b[w+p,2]:=b[i,2]-1;

end;

if not m2[b[i,1]+1,b[i,2]]

then begin

inc(p);

m2[b[i,1]+1,b[i,2]]:=true;

b[w+p,1]:=b[i,1]+1;

b[w+p,2]:=b[i,2];

end;

if not m2[b[i,1],b[i,2]+1]

then begin

inc(p);

m2[b[i,1],b[i,2]+1]:=true;

b[w+p,1]:=b[i,1];

b[w+p,2]:=b[i,2]+1;

end;

end;

q:=w+1;

w:=w+p;

p:=0;

until q>w;

write(-1);

end.

#4 虽然离开@2011-10-27 02:36:00
回复 删除
这道题只是一个时间点不能走,过了这个时间点后,就可以走
#5 ZLTJOHN@2012-09-11 22:24:00
回复 删除
哦,我懂了,谢谢
查看更多回复
提交回复