ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1254. Die Hard

why "WA7"?
Posted by vgu 5 Feb 2008 17:50
{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1}
program Project5;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const cn: array [0..1] of extended=(1,1.414213562373095);
      dx: array [1..8] of integer=(-1,0,1,1,1,0,-1,-1);
      dy: array [1..8] of integer=(-1,-1,-1,0,1,1,1,0);

var a: array [0..76,0..76] of byte;
    i,j,n,m,k,x,y,x1,y1: integer;
    v,s,res: extended;
    ch: char;
    flag: boolean;

  procedure wave(x,y,x1,y1,n,m: integer; var res: extended; var flag: boolean);
  var fl: array [0..76,0..76] of byte;
      r: array [0..76,0..76] of extended;
      och: array [1..6000,1..2] of integer;
      i,j,b,e,xz,yz: integer;
  begin
    flag:=false;
    For i:=1 to n do
      For j:=1 to m do
        begin
        fl[i,j]:=0;
        r[i,j]:=0;
        end;
    b:=1;
    e:=1;
    och[b,1]:=x;
    och[b,2]:=y;
    fl[y,x]:=1;
    while b<=e do
      begin
      If (och[b,1]=x1) and (och[b,2]=y1) then
        begin
        flag:=true;
        break;
        end;
      For i:=1 to 8 do
        begin
        xz:=och[b,1]+dx[i];
        yz:=och[b,2]+dy[i];
        If (a[yz,xz]=0) and (xz>0) and (xz<=m) and (yz>0) and (yz<=n) then
          begin
          If fl[yz,xz]=0 then
            begin
            inc(e);
            och[e,1]:=xz;
            och[e,2]:=yz;
            r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2];
            fl[yz,xz]:=1;
            end
            else
            If r[yz,xz]>r[och[b,2],och[b,1]]+cn[i mod 2] then
              r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2];
          end;
        end;
      inc(b);
      end;
    If flag then
      res:=r[y1,x1]
      else
      res:=0;
  end;

begin
  readln(m,n,k,v);
  For i:=1 to n do
    begin
    For j:=1 to m do
      begin
      read(ch);
      If ch='#' then
        a[i,j]:=1
        else
        a[i,j]:=0;
      end;
    readln;
    end;
  s:=0;
  readln(x,y);
  For i:=1 to k do
    begin
    readln(x1,y1);
    wave(x,y,x1,y1,n,m,res,flag);
    If flag then
      begin
      x:=x1;
      y:=y1;
      s:=s+res;
      end;
    end;
  write((s/v):0:2);
end.
Re: why "WA7"?
Posted by vgu 6 Feb 2008 15:43
AC now
Re: why "WA7"?
Posted by sdf 1 May 2009 14:44
I have wa7 too.
I used dijkstra.
Give me hint, I can't find mistake :(((