|
ctsc2000之《冰原探险》解题报告
福建师大附中 方润
问题分析：
问题要求把冰块从起点推到终点最少次数，可以用坐标（ｘ，ｙ）表示冰块位置的每一种状态。根据题目要求，冰块必须再碰到冰山时才能停下，所以我们就可以算出冰山从每一格，分别向四个方向推，可到达的位置。所以问题就可以用广度搜索来解决。
算法：
采用队结构，依次扩展出每一个结点的所能到达的所有结点。为了在让结束条件更简单，我们可以把终点看作是一块边长为一的小冰山。这样在在冰块撞到这块小冰山时，程序就找到了正确解。如果无法继续扩展队中的点，即队的头指针等于尾指针，就输出无解。在计算冰块能到达的位置时，可以朝一个方向搜索，直到找到一块能挡住冰块前进的冰山为止。
例如再输入样例中队的扩展情况如下：
1， 1-》2，1-》2，5-》4，5
再扩展到4，5时，冰块撞到了代表终点的小冰山，所以样例的最优值就是3。
算法优化：
由于数据在地图的大小上没有限制，不能以一个二维数组来表示地形，所以在计算冰块可到达位置时只能对所有冰山进行搜索。
为了提高在计算冰块可到达的位置时速度，可以在开始时按每一个方块的四个坐标先进行了四次排序，这样在计算时只要依次查找每一块冰山，再找到一块能挡住冰块前进冰山后，冰块就停在此冰山的前面。
还可以记录下每个结点的父亲，避免冰块来回在一个地方移动。在扩展的每一个结点与前面所有结点进行比较，避免重复。
在空间上，可以把一个冰山记录在一个指针里。这样在四次排序中，只要对指针的地址进行排序。
总结：
本题算法没有什么特别，但编写起来比较麻烦。
程序：
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
const filein='ctsc2000\ice\ice.00a';
{ctsc2000\ice\ice.oua}
type xy=record
x,y:integer;
end;
arrfa=array[1..8000]of byte;
arrd=record
x1,y1,x2,y2:integer;
end;
ard=^arrd;
var dl,dr,du,dd:array[1..4000]of ard;
st,en:xy;
n,bro:integer;
procedure ql(x,y:integer);
var i,j,k:integer;
p:ard;
begin
i:=x;
j:=y;
k:=dl[(x+y)div 2]^.x1;
repeat
while dl[i]^.x1<k do inc(i);
while dl[j]^.x1>k do dec(j);
if i<=j then
begin
p:=dl[i];
dl[i]:=dl[j];
dl[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<y then ql(i,y);
if j>x then ql(x,j);
end;
procedure qr(x,y:integer);
var i,j,k:integer;
p:ard;
begin
i:=x;
j:=y;
k:=dr[(x+y)div 2]^.x2;
repeat
while dr[i]^.x2<k do inc(i);
while dr[j]^.x2>k do dec(j);
if i<=j then
begin
p:=dr[i];
dr[i]:=dr[j];
dr[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<y then qr(i,y);
if j>x then qr(x,j);
end;
procedure qu(x,y:integer);
var i,j,k:integer;
p:ard;
begin
i:=x;
j:=y;
k:=du[(x+y)div 2]^.y1;
repeat
while du[i]^.y1<k do inc(i);
while du[j]^.y1>k do dec(j);
if i<=j then
begin
p:=du[i];
du[i]:=du[j];
du[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<y then qu(i,y);
if j>x then qu(x,j);
end;
procedure qd(x,y:integer);
var i,j,k:integer;
p:ard;
begin
i:=x;
j:=y;
k:=dd[(x+y)div 2]^.y2;
repeat
while dd[i]^.y2<k do inc(i);
while dd[j]^.y2>k do dec(j);
if i<=j then
begin
p:=dd[i];
dd[i]:=dd[j];
dd[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<y then qd(i,y);
if j>x then qd(x,j);
end;
procedure init;
var i:integer;
begin
assign(input,filein);
reset(input);
readln(n);
readln(st.x,st.y);
readln(en.x,en.y);
for i:=1 to n do
new(dl[i]);
for i:=1 to n do
begin
readln(dl[i]^.x1,dl[i]^.y1,dl[i]^.x2,dl[i]^.y2);
dr[i]:=dl[i];
du[i]:=dl[i];
dd[i]:=dl[i];
end;
inc(n);
new(dl[n]);
dl[n]^.x1:=en.x;
dl[n]^.x2:=en.x;
dl[n]^.y1:=en.y;
dl[n]^.y2:=en.y;
dr[n]:=dl[n];
du[n]:=dl[n];
dd[n]:=dl[n];
ql(1,n);
qr(1,n);
qu(1,n);
qd(1,n);
close(input);
end;
procedure get(p:xy;f:byte;var re:xy);
var i:integer;
begin
bro:=0;
case f of
1: begin
re.x:=p.x;
i:=0;
repeat
inc(i);
until(i>n)or((dd[i]^.y1>p.y)and(dd[i]^.x1<=p.x)and(dd[i]^.x2>=p.x));
if i=n+1 then bro:=1
else begin
re.y:=dd[i]^.y1-1;
if (dd[i]^.x1=en.x)and(dd[i]^.y1=en.y)then bro:=-1;
end;
end;
2: begin
re.y:=p.y;
i:=1;
repeat
inc(i);
until(i>n)or((dl[i]^.x1>p.x)and(dl[i]^.y1<=p.y)and(dl[i]^.y2>=p.y));
if i=n+1 then bro:=1
else begin
re.x:=dl[i]^.x1-1;
if (dl[i]^.x1=en.x)and(dl[i]^.y1=en.y)then bro:=-1;
end;
end;
3: begin
re.x:=p.x;
i:=n+1;
repeat
dec(i);
until(i=0)or((du[i]^.y2<p.y)and(du[i]^.x1<=p.x)and(du[i]^.x2>=p.x));
if i=0 then bro:=1
else begin
re.y:=du[i]^.y2+1;
if (du[i]^.x1=en.x)and(du[i]^.y1=en.y)then bro:=-1;
end;
end;
4: begin
re.y:=p.y;
i:=n+1;
repeat
dec(i);
until(i=0)or((dr[i]^.x2<p.x)and(dr[i]^.y1<=p.y)and(dr[i]^.y2>=p.y));
if i=0 then bro:=1
else begin
re.x:=dr[i]^.x2+1;
if (dr[i]^.x1=en.x)and(dr[i]^.y1=en.y)then bro:=-1;
end;
end;
end;
end;
procedure do1;
var a:array[1..8000]of xy;
fa:arrfa;
h1,h2,l,i,t,j,k:integer;
re:xy;
function ok(r:xy):boolean;
var i:integer;
begin
ok:=false;
for i:=1 to l do
if (a[i].x=r.x)and(a[i].y=r.y) then exit;
ok:=true;
end;
begin
h1:=1;
h2:=1;
l:=1;
a[1]:=st;
fa[1]:=0;
t:=0;
repeat
inc(t);
for i:=h1 to h2 do
for j:=1 to 4 do
if j<>fa[i] then
begin
get(a[i],j,re);
if bro=-1 then
begin
writeln(t);
halt;
end;
if (bro=0)and(ok(re)) then
begin
inc(l); { 1 }
a[l]:=re; {4 2}
fa[l]:=(j+1)mod 4+1; { 3 }
end;
end;
h1:=h2+1;
h2:=l;
until(h1>h2);
writeln(0);
end;
begin
init;
do1;
end.
|
|
