想了很久....实在不懂哪里是图结构......
由于题目没给出数据范围....
所以用矩阵记录地图是不可能的....
记录到达每个冰山4个方向的最少步数....
便可求出结果.....
朱全民老师的<奥赛经典>里面就有这道题...
program project104；
type
data=record
x1,y1,x2,y2:longint；
end；
var
p1,p2:array[1..16000]of longint；
p:array[1..4000,1..4]of longint；
a:array[1..4000]of data；
min,op,ed,i,j,k,n,kk,k1,k2,ff,d,xx1,xx2,yy1,yy2,x,y,ox1,ox2,oy1,oy2:longint；
procedure init；
begin
readln(n)；
readln(xx1,yy1)；
readln(xx2,yy2)；
for i:=1 to n do
with a[i] do readln(x1,y1,x2,y2)；
for i:=1 to n do
for j:=1 to 4 do p[i,j]:=maxint；
end；
procedure addin(k,f,o,s:integer)；
begin
if (o<>maxint)and(o<>-maxint)then
if p[k,f]=maxint then
begin
inc(ed)；
p[k,f]:=s+1；
p1[ed]:=k；
p2[ed]:=f；
end；
end；
procedure main；
begin
min:=maxint；
op:=1；
ed:=0；
x:=xx1；
y:=yy1；
oy1:=maxint；
oy2:=-maxint；
for j:=1 to n do
if (a[j].x1<=x)and(a[j].x2>=x)then
begin
if (a[j].y1<oy1)and(a[j].y1>y)then
begin
oy1:=a[j].y1；
k1:=j；
end
else if (a[j].y2>oy2)and(a[j].y2<y)then
begin
oy2:=a[j].y2；
k2:=j；
end；
end；
addin(k1,3,oy1,0)；
addin(k2,4,oy2,0)；
if (xx2=x)and(oy1>=yy2)and(oy2<=yy2)then min:=1；
ox1:=maxint；
ox2:=-maxint；
for j:=1 to n do
if (a[j].y1<=y)and(a[j].y2>=y)then
begin
if (a[j].x1<ox1)and(a[j].x1>x)then
begin
ox1:=a[j].x1；
k1:=j；
end
else if (a[j].x2>ox2)and(a[j].x2<x)then
begin
ox2:=a[j].x2；
k2:=j；
end；
end；
addin(k1,1,ox1,0)；
addin(k2,2,ox2,0)；
if (yy2=y)and(ox1>=xx2)and(ox2<=xx2)then min:=1；
while op<=ed do
begin
kk:=p1[op]；
ff:=p2[op]；
if ff<=2 then
begin
if ff=1 then x:=a[kk].x1-1
else x:=a[kk].x2+1；
y:=a[kk].y1；
oy1:=maxint；
oy2:=-maxint；
for j:=1 to n do
if (a[j].x1<=x)and(a[j].x2>=x)then
begin
if (a[j].y1<oy1)and(a[j].y1>y)then
begin
oy1:=a[j].y1；
k1:=j；
end
else if (a[j].y2>oy2)and(a[j].y2<y)then
begin
oy2:=a[j].y2；
k2:=j；
end；
end；
addin(k1,3,oy1,p[kk,ff])；
addin(k2,4,oy2,p[kk,ff])；
if (xx2=x)and(oy1>=yy2)and(oy2<=yy2)then min:=p[kk,ff]+1；
end
else
begin
if ff=3 then y:=a[kk].y1-1
else y:=a[kk].y2+1；
x:=a[kk].x1；
ox1:=maxint；
ox2:=-maxint；
for j:=1 to n do
if (a[j].y1<=y)and(a[j].y2>=y)then
begin
if (a[j].x1<ox1)and(a[j].x1>x)then
begin
ox1:=a[j].x1；
k1:=j；
end
else if (a[j].x2>ox2)and(a[j].x2<x)then
begin
ox2:=a[j].x2；
k2:=j；
end；
end；
addin(k1,1,ox1,p[kk,ff])；
addin(k2,2,ox2,p[kk,ff])；
if (yy2=y)and(ox1>=xx2)and(ox2<=xx2)then min:=p[kk,ff]+1；
end；
inc(op)；
end；
end；
begin
init；
main；
if min<>maxint then writeln(min)
else writeln(’0’)；
end.