Edited by author 26.12.2006 16:16

(1,1)
it is left up corner
or left down???
(Wa4)

Wrong BFS.
AC now!

Edited by author 03.08.2005 13:10

I've found my mistake... Really stupid

Edited by author 19.06.2005 14:57

My program get WA #4. Give me some tests, please.
This is main part of my solution:

    L := 0;
    read(S.y,S.x);
    for i := 1 to k do begin
        read(F.y,F.x);
        cL := BFS(S,F);
        if cL=-1 then
            Continue;
        S := F;
        L := L+cL;
    end;
    L := L/V;
    write(L:0:2);

This is my program.

Program Ural1254;
  Const
    Up:Array[1..8, 1..2] Of Integer=((1, 0), (0, 1), (-1, 0), (0, -1),
                                     (1, 1), (1, -1), (-1, 1), (-1, -
1));
  Type
    Rec=Record
          X, Y:Byte;
          Long:Real;
        End;
  Var
    P2, V:Real;
    M, N, K:Integer;
    Map:Array[1..75, 1..75] Of Char;
    Bomb:Array[0..1000, 1..2] Of Integer;
    Buf:Array[1..5625] Of Rec;
    Gone:Array[1..75, 1..75] Of Boolean;

  Procedure Init;
    Var
      A, B:Integer;
    Begin
      P2:=Sqrt(2);
      Readln(M, N, K, V);
      For A:=1 To N Do
        Begin
          For B:=1 To M Do Read(Map[A, B]);
          Readln;
        End;
      Readln(Bomb[0, 1], Bomb[0, 2]);
      For A:=1 To K Do Readln(Bomb[A, 1], Bomb[A, 2]);
    End;

  Procedure Main;
    Var
      Where, Step, NowFa:Integer;
      Done:Boolean;
      Total:Real;

    Procedure Search;
      Var
        A, NowX, NowY:Integer;

      Function OK(X, Y:Integer):Boolean;
        Begin
          If (X>0) And (Y>0) And (X<=M) And (Y<=N) And Not Gone[Y, X]
          And(Map[Y, X]='.') Then OK:=True
            Else OK:=False;
        End;

      Begin
        For A:=1 To 8 Do
          Begin
            NowX:=Buf[NowFa].X+Up[A, 1];
            NowY:=Buf[NowFa].Y+Up[A, 2];
            If OK(NowX, NowY) Then
              Begin
                Gone[NowY, NowX]:=True;
                Inc(Step);
                Buf[Step].X:=NowX;
                Buf[Step].Y:=NowY;
                If A>4 Then Buf[Step].Long:=Buf[NowFa].Long+P2
                  Else Buf[Step].Long:=Buf[NowFa].Long+1;
                If (NowX=Bomb[Where+1, 1]) And (NowY=Bomb[Where+1,
2]) Then
                  Begin
                    Done:=True;
                    Exit;
                  End;
              End;
          End;
      End;

    Begin
      Total:=0;
      For Where:=0 To K-1 Do
        Begin
          FillChar(Buf, SizeOf(Buf), 0);
          FillChar(Gone, SizeOf(Gone), False);
          NowFa:=1;
          Step:=1;
          Buf[NowFa].X:=Bomb[Where, 1];
          Buf[NowFa].Y:=Bomb[Where, 2];
          Gone[Bomb[Where, 2], Bomb[Where, 1]]:=True;
          Done:=False;
          Repeat
            Search;
            Inc(NowFa);
          Until Done;
          Total:=Total+Buf[Step].Long;
        End;
      Writeln(Total/V:0:2);
    End;

  Begin
    Init;
    Main;
  End.

1.......*...........
........*...........
********............
....................
...................2
Is It Possible to get from point 1 to point 2???
email : caa@baga.ac.net.ru

Aidin_n7@hotmail.com
~~~~~~

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.

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.

u can get AC in 2.593 sec
by only search(like bfs) and bound : )

I understand the problem like that :
The first way is :
J 1 0 0
# # 2 0
B 3 0 0

So the time needed is
3 * 1.23 = 3.69

The second :
0 0 0 B
# # 2 0
J 1 0 0

Here the time
2 * 1.23 = 2.64
Total = 2.46 + 3.69 = 6.29

The third :
0 0 0 J
# # 0 1
0 0 0 B

time = 1.23
total = >>>> 7.52 <<<<< ????!!!!!

the answer in the sample isn't even a multiple of v ??!!!
WOuld You be so kind and explain it to me ??

 Please help me! I use the usual BFS for solve this task, but got WA!
May be someone can give some tests?

I got TLE at 17 sec (TL for 1254 is 20 sec)

360228 | 19:29:20 22 Mar 2003 | Nazar Revutsky | 1254 | Pascal | Time
Limit Exceeded | 17.184 sec | 94K

const z:array[1..8,1..2]of integer=((-1,-1),(-1,0),(-1,1),(0,1),
(1,1),(1,0),(1,-1),(0,-1));
var
tab:array[0..76,0..76] of boolean;
r:array[1..75,1..75] of real;
v,q2,sum,psum:real;
i,j,jj,k,x0,y0,x,y:integer;
m,n:integer;
c:char;

procedure find;
type rec=record
     x,y:integer;
    end;
var i,j,top1,top2:integer;
    st1,st2:array[1..1700] of rec;
    a1,a2:integer;
begin
top1:=1;
top2:=0;
st1[1].x:=x0;
st1[1].y:=y0;

repeat
for i:=1 to top1 do begin
if (st1[i].x=x)and(st1[i].y=y) then begin
                               sum:=sum+r[x,y];
                               exit;
                               end;
for j:=1 to 8 do begin
a1:=st1[i].x+z[j,1];
a2:=st1[i].y+z[j,2];
if (tab[a1,a2]=false)and(r[a1,a2]<0) then begin
   inc(top2);
   st2[top2].x:=a1;
   st2[top2].y:=a2;
   if (z[j,1]<>0)and(z[j,2]<>0) then  r[a1,a2]:=r[st1[i].x,st1[i].y]
+q2
   else r[a1,a2]:=r[st1[i].x,st1[i].y]+1;
   end;
end;
end;
st1:=st2;
top1:=top2;
top2:=0;
until top1=0;
end;


begin
q2:=sqrt(2);
readln(m,n,k,v);
for i:=0 to n+1 do
for j:=0 to m+1 do
tab[i,j]:=true;
for i:=1 to n do begin
for j:=1 to m do begin
read(c);
if c='.' then tab[i,j]:=false;
end;
readln;
end;
readln(y0,x0);

for i:=1 to k do  begin
for j:=1 to n do
for jj:=1 to m do
r[j,jj]:=-1;
readln(y,x);
r[x0,y0]:=0.0000001;
psum:=sum;
find;
if abs(sum-psum)>0.5 then begin
x0:=x;
y0:=y;
end;
end;
sum:=sum/v;
writeln(sum:0:2);
end.