P1366冰原探险Wrong Answer
描述
传说中，南极有一片广阔的冰原，在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相等的方格。在这个冰原上有N个大小不等的矩形冰山，这些巨大的冰山有着和南极一样古老的历史，每个矩形冰山至少占据一个方格，且其必定完整地占据方格。冰山和冰山之间不会重叠，也不会有边或点相连。以下两种情况均是不可能出现的：
ACM探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料，在这个冰原上一个大小为一格的深洞中，藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可移动的小冰块。显然，在南极是不可能有这样小的独立冰块的，所以这块冰块也一定是史前文明的产物。他们在想办法把这个冰块推到洞里去，这样就可以打开一条通往冰原底部的通道，发掘史前文明的秘密。冰块的起始位置与深洞的位置均不和任何冰山相邻。
这个冰原上的冰面和冰山都是完全光滑的，轻轻的推动冰块就可以使这个冰块向前滑行，直到撞到一座冰山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域，也可以从两座冰山之间穿过（见下图）。冰块只能沿网格方向推动。
图片
格式
输入格式

输入文件第一行为冰山的个数N (1<=N<=4000)，第二行为冰块开始所在的方格坐标X1,Y1，第三行为深洞所在的方格坐标X2,Y2，以下N行每行有四个数，分别是每个冰山所占的格子左上角和右下角坐标Xi1,Yi1,Xi2,Yi2
输出格式

输出文件仅包含一个整数，为最少推动冰块的次数。如果无法将冰块推入深洞中，则输出0。
样例1
样例输入1[复制]

2
1 1
5 5
1 3 3 3
6 2 8 4
样例输出1[复制]

3
限制
各个测试点1s
提示
寻求好的搜索方法

代码：

const
filein = 'ice.in';
fileout = 'ice.out';
up = 1;left = 2;right = 3;down = 4;
move : array[1..4, 1..2]of byte = ((left, right), (up, down), (up, down), (left, right));
move2 : array[1..4, 1..2]of byte = ((up, down), (left, right), (left, right), (up, down));
type
ticeberg = record
x1, y1, x2, y2 : integer;
end;
tstate = record
ibid : word;
bor : byte;
end;
var
already : array[1..4000, 1..4]of boolean;
iceberg : array[1..4001]of ticeberg;
a1, a2 : array[1..1000]of tstate;
step, n, q1, q2 : word;
srcx, srcy, tarx, tary : integer;
time : longint;
procedure initialize;
var f : text; b : boolean; i : word;
begin
readln( n);
readln( srcx, srcy);
readln( tarx, tary);
b := true;
for i := 1 to n do
with iceberg[i] do
readln( x1, y1, x2, y2);
with iceberg[n + 1] do
begin
x1 := tarx; x2 := x1;
y1 := tary; y2 := y1;
end;
end;
procedure out;
var f : text;
begin
writeln( step);
halt;
end;
procedure expandsrc(p : byte; var p1, p2 : word);
var i, j : word;
m1, m2 : integer;
begin
p1 := 0; p2 := 0;
j := 0;
if (p = up) or (p = down) then
begin
m1 := -maxint; m2 := maxint;
for i := 1 to n + 1 do
begin
if (iceberg[i].x1 <= srcx) and (iceberg[i].x2 >= srcx) then
if (iceberg[i].y2 + 1 < srcy) and (iceberg[i].y2 + 1 > m1) then
begin m1 := iceberg[i].y2; p1 := i; end;
if (iceberg[i].x1 <= srcx) and (iceberg[i].x2 >= srcx) then
if (iceberg[i].y1 - 1 > srcy) and (iceberg[i].y1 - 1 < m2) then
begin m2 := iceberg[i].y1; p2 := i; end;
end;
end
else
begin
m1 := -maxint; m2 := maxint;
for i := 1 to n + 1 do
begin
if (iceberg[i].y1 <= srcy) and (iceberg[i].y2 >= srcy) then
if (iceberg[i].x2 + 1 < srcx) and (iceberg[i].x2 + 1 > m1) then
begin m1 := iceberg[i].x2; p1 := i; end;
if (iceberg[i].y1 <= srcy) and (iceberg[i].y2 >= srcy) then
if (iceberg[i].x1 - 1 > srcx) and (iceberg[i].x1 - 1 < m2) then
begin m2 := iceberg[i].x1; p2 := i; end;
end;
end;
if (p1 = n + 1) or (p2 = n + 1) then out;
end;
procedure expand(id : word; q : byte; var p1, p2 : word);
var i : word;
x, y, m1, m2 : integer;
begin
p1 := 0; p2 := 0;
case q of
up : begin x := iceberg[id].x1; y := iceberg[id].y1 - 1; end;
down : begin x := iceberg[id].x2; y := iceberg[id].y2 + 1; end;
right : begin x := iceberg[id].x2 + 1; y := iceberg[id].y2; end;
left : begin x := iceberg[id].x1 - 1; y := iceberg[id].y1; end;
end;
if (q = left) or (q = right) then
begin
m1 := -maxint; m2 := maxint;
for i := 1 to n + 1 do
begin
if (iceberg[i].x1 <= x) and (iceberg[i].x2 >= x) then
if (iceberg[i].y2 + 1 < y) and (iceberg[i].y2 + 1 > m1) then
begin m1 := iceberg[i].y2; p1 := i; end;
if (iceberg[i].x1 <= x) and (iceberg[i].x2 >= x) then
if (iceberg[i].y1 - 1 > y) and (iceberg[i].y1 - 1 < m2) then
begin m2 := iceberg[i].y1; p2 := i; end;
end;
end
else
begin
m1 := -maxint; m2 := maxint;
for i := 1 to n + 1 do
begin
if (iceberg[i].y1 <= y) and (iceberg[i].y2 >= y) then
if (iceberg[i].x2 + 1 < x) and (iceberg[i].x2 + 1 > m1) then
begin m1 := iceberg[i].x2; p1 := i; end;
if (iceberg[i].y1 <= y) and (iceberg[i].y2 >= y) then
if (iceberg[i].x1 - 1 > x) and (iceberg[i].x1 - 1 < m2) then
begin m2 := iceberg[i].x1; p2 := i; end;
end;
end;
if (p1 = n + 1) or (p2 = n + 1) then out;
end;
procedure firstexpand;
var i, b : byte;
next1, next2 : word;
begin
step := 1;
for i := up to left do
begin
expandsrc(i, next1, next2);
b := 5 - move2[i, 1];
if next1 <> 0 then
begin
inc(q1);
a1[q1].ibid := next1;
a1[q1].bor := b;
already[next1, b] := true
end;
b := 5 - move2[i, 2];
if next2 <> 0 then
begin
inc(q1);
a1[q1].ibid := next2;
a1[q1].bor := b;
already[next2, b] := true
end;
end;
end;
procedure mainexpand;
var i : word;
j, b : byte;
next1, next2 : word;
begin
repeat
inc(step);
for i := 1 to q1 do
begin
expand(a1[i].ibid, a1[i].bor, next1, next2);
b := 5 - move[a1[i].bor, 1];
if next1 <> 0 then
if not already[next1, b] then
begin
inc(q2);
a2[q2].ibid := next1;
a2[q2].bor := b;
already[next1, b] := true
end;
b := 5 - move[a1[i].bor, 2];
if next2 <> 0 then
if not already[next2, b] then
begin
inc(q2);
a2[q2].ibid := next2;
a2[q2].bor := b;
already[next2, b] := true
end
end;
if q2 = 0 then break;
a1 := a2; q1 := q2;
q2 := 0;
until false;
end;
procedure outfailed;
var f : text;
begin
writeln( 0);
close(f);
end;
begin
initialize;
firstexpand;
mainexpand;
outfailed;

end.

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 872 KiB, score = 10
测试数据 #4: WrongAnswer, time = 0 ms, mem = 876 KiB, score = 0
测试数据 #5: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 872 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 872 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 868 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 872 KiB, score = 10

WrongAnswer, time = 185 ms, mem = 876 KiB, score = 90

为什么第四个点不过？