why WA in 1.61sec??? I know it meant in last tests but why WA?
Posted by
Pasha 18 Apr 2003 20:22
Const
MaxN = 77;
B : Array[1..8,1..2] Of ShortInt =
((0 ,-1),(-1, 0),( 1, 0),( 0, 1),
(-1,-1),( 1,-1),(-1, 1),( 1, 1));
Type
Point = record
X, Y : Byte;
End;
Board = Array[0..Maxn,0..Maxn] Of Boolean;
Var
A : Board;
M, N, J, X1, X2, Y1,
Y2 : Byte;
K, I : Integer;
V, Ans, SQRT2 : Real;
Ch : Char;
Function BFS:Boolean;
Var
I, Q1, Q2, Xt, Yt : Integer;
Q : Array[0..MaxN*MaxN] Of Point;
Mark : Board;
R : Array[0..Maxn,0..Maxn] Of Real;
Begin
Mark := A;
If Mark[X2][Y2] then While True do;
{Check whether it is true that all bombs are
outside the buildings?}
Mark[X1][Y1] := True;
R[X1][Y1] := 0 ;
Q[1].X := X1; Q[1].Y := Y1;
Q1 := 1 ; Q2 := 1 ;
While (Q1<=Q2) And (Not Mark[X2][Y2]) Do
Begin
For I := 1 To 8 Do
Begin
Xt := Q[Q1].X+B[I][1];
Yt := Q[Q1].Y+B[I][2];
If ((0<Xt) and (Xt<=M)) and
((0<Yt) and (Yt<=N)) and
(Not Mark[Xt][Yt]) Then
Begin
Mark[Xt][Yt] := True;
Inc(Q2);
Q[Q2].X := Xt; Q[Q2].Y := Yt;
If I>4 Then
R[Xt][Yt] := R[Q[Q1].X][Q[Q1].Y]+SQRT2
Else
R[Xt][Yt] := R[Q[Q1].X][Q[Q1].Y]+1;
End;
End;
Inc(Q1);
End;
BFS := Mark[X2][Y2];
If Mark[X2][Y2] Then
Ans := Ans+ R[X2][Y2];
End;
begin
SQRT2 := SQRT(2);
ReadLn(N, M, K, V);
For I := 1 To M Do
Begin
For J := 1 To N Do
Begin
Read(Ch);
A[I][J] := Ch='#';
End;
ReadLn;
End;
ReadLn(Y1,X1);
For I := 1 To K Do
Begin
ReadLn(Y2,X2);
If BFS Then {From Y1,X1 To Y2,X2}
Begin X1:=X2; Y1:=Y2; End;
End;
Ans := Ans/V;
WriteLn(Ans:0:2);
ReadLn;
End.