ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1254. Крепкий орешек

is there any1 here can help me ? I still don`t know why BFS doesn`t work and WA in last test?!!!
Послано Locomotive 22 апр 2003 16:31
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.
Your BFS is not correct
Послано Mad Mouse 3 май 2003 18:38
Your BFS is not correct. Your mistake is that if you find a shorter
way to checked cell, you don't go to it. It is not right. Change the
condition
    Not Mark[Xt][Yt]
by the condition
    R[Xt][Yt]  <  new R[Xt][Yt] (value that you write in R)
and you'll get AC (I hope :)

--
Best regards
Mad Mouse (madmouse@udm.ru)