Common Board @ Timus Online Judge

===PROBLEM 1171===Why I get WA?Please, help me!!!!!!! (+)

Posted by Nazarov Denis (nsc2001@rambler.ru) 18 Feb 2002 16:04

Program t1171;{$N+}

Const MaxN = 16;
       MaxD = 256;
       CAdd : array[1..4]of byte=(1,4,16,64);

Type Integer = SmallInt;
      SStr    = array[1..5]of byte;
      Floor   = array[1..4,1..4]of integer;
      SFloor = array[1..4,1..4]of SStr;

Var   St          : array[1..MaxN]of record
                      F : Floor;
                      D : Floor;
                    end;
      A           : array[0..MaxD,1..MaxN+1]of Floor;
      A2          : array[0..MaxD,1..MaxN+1]of SFloor;
      CurPath     : String[16];
      PSearch     : Floor;
      Tmp         : SStr;
      R,C,N       : integer;

Function ConvertFromByte(A : SStr) : String;
Var i,j,b,k : byte;
    sb      : array[1..16]of byte;
    s       : string[16];
begin
s:='';
for j:=1 to 4 do begin
   b:=A[j+1];
   for i:=1 to 4 do begin
    k:=b mod 4;
    b:=b div 4;
    Case k of
     0 : s:=s+'W';
     1 : s:=s+'E';
     2 : s:=s+'S';
     3 : s:=s+'N';
    end;
   end;
end;
s:=copy(s,1,A[1]);
ConvertFromByte:=s;
end;

Procedure ConvertInByte(S : String;Var A : SStr);
Var i,j   : byte;
    sb    : array[1..16]of byte;
begin
fillchar(sb,sizeof(sb),0);
fillchar(A,sizeof(A),0);
A[1]:=Length(S);
for i:=1 to length(s) do
   Case s[i] of
    'W' : sb[i]:=0;
    'E' : sb[i]:=1;
    'S' : sb[i]:=2;
    'N' : sb[i]:=3;
   end;
for i:=1 to 16 do begin
   j:=i mod 4;
   if j=0 then j:=4;
   A[(i+7) div 4]:=A[(i+7) div 4]+sb[i]*CAdd[j];
end;
end;

Function Can(i,j : integer) : boolean;
begin
Can:=(i>0)and(i<5)and(j>0)and(j<5);
end;

Function Can2(i,j,c : integer) : boolean;
begin
Can2:=(i>0)and(i<5)and(j>0)and(j<5)and(c<=N);
end;

Procedure FullSearch(I,J,CurI,CurJ,CurD,CurF,CurL : integer;Path :
string);
Var u       : integer;
    CurPath : string[16];
   Procedure Go(dI,dJ : integer);
    begin
     if Not(Can(CurI+dI,CurJ+dJ)) then exit;
     if PSearch[CurI+dI,CurJ+dJ]=1 then exit;
     if dJ=1 then CurPath:='E' + CurPath;
     if dJ=-1 then CurPath:='W' + CurPath;
     if dI=1 then CurPath:='S' + CurPath;
     if dI=-1 then CurPath:='N' + CurPath;
     FullSearch(I,J,CurI+dI,CurJ+dJ,CurD+1,CurF+St[CurL].F
[CurI+dI,CurJ+dJ],CurL,CurPath);
    end;
begin
CurPath:=Path;
for u:=0 to MaxD-CurD do
   if A[u,CurL+1,I,J]<>-1 then
    if A[u+CurD,CurL,CurI,CurJ]<CurF+A[u,CurL+1,I,J] then begin
     A[u+CurD,CurL,CurI,CurJ]:=CurF+A[u,CurL+1,I,J];
     ConvertInByte(CurPath,Tmp);
     A2[u+CurD,CurL,CurI,CurJ]:=Tmp;
    end;
PSearch[CurI,CurJ]:=1;
   Go(-1,0); CurPath:=Path;
   Go(1,0); CurPath:=Path;
   Go(0,-1); CurPath:=Path;
   Go(0,1); CurPath:=Path;
PSearch[CurI,CurJ]:=0;
end;

Procedure Init;
Var m,k,i,j,p : integer;
begin
Read(N);
for k:=N downto 1 do begin
   for i:=1 to 4 do
    for j:=1 to 4 do
     Read(St[k].F[i,j]);
   for i:=1 to 4 do
    for j:=1 to 4 do
     Read(St[k].D[i,j]);
end;
Read(R,C);
for m:=0 to MaxD do
   for k:=1 to MaxN+1 do
    for i:=1 to 4 do
     for j:=1 to 4 do
      A[m,k,i,j]:=-1;
fillchar(A2,SizeOf(A2),0);
A[0,N+1,R,C]:=0;
end;

Function RestorePath(ti,tj,td : integer) : string;
Var ci,cj,cd,cz,v : integer;
    Ans,S         : string[255];
begin
ci:=ti;
cj:=tj;
cd:=td;
cz:=1;
Ans:='';
While True do begin
    if cz=N+1 then break;
    if cz>1 then Ans:='D' + Ans;
    S:=ConvertFromByte(A2[cd,cz,ci,cj]);
    Ans:=S + Ans;
    cd:=cd-Length(S)-1;
    cz:=cz+1;
    for v:=1 to length(S) do
     Case S[v] of
      'W' : cj:=cj+1;
      'E' : cj:=cj-1;
      'S' : ci:=ci-1;
      'N' : ci:=ci+1;
     end;
   end;
RestorePath:=Ans;
end;

Procedure Solve;
Var k,i,j    : integer;
    max      : extended;
    mi,mj,md : integer;
begin
CurPath:='';
FillChar(PSearch,SizeOf(PSearch),0);
FullSearch(R,C,R,C,1,St[N].F[

I change my program but I still get WA ! Please, help me(+)

Posted by Nazarov Denis (nsc2001@rambler.ru) 18 Feb 2002 16:50

Program t1171;{$N+}

Const MaxN = 16;
       MaxD = 256;
       CAdd : array[1..4]of byte=(1,4,16,64);

Type Integer = SmallInt;
      SStr    = array[1..5]of byte;
      AStr    = array[1..2]of byte;
      Floor   = array[1..4,1..4]of integer;
      SFloor = array[1..4,1..4]of SStr;
      AFloor = array[1..4,1..4]of AStr;

Var   St          : array[1..MaxN]of record
                      F : Floor;
                      D : Floor;
                    end;
      A           : array[0..MaxD,1..MaxN+1]of Floor;
      A2          : array[0..MaxD,1..MaxN+1]of SFloor;
      A3          : array[1..MaxN+1]of SFloor;
      CurPath     : String[16];
      PSearch     : Floor;
      Tmp         : SStr;
      R,C,N       : integer;

Function ConvertFromByte(A : SStr) : String;
Var i,j,b,k : byte;
    sb      : array[1..16]of byte;
    s       : string[16];
begin
s:='';
for j:=1 to 4 do begin
   b:=A[j+1];
   for i:=1 to 4 do begin
    k:=b mod 4;
    b:=b div 4;
    Case k of
     0 : s:=s+'W';
     1 : s:=s+'E';
     2 : s:=s+'S';
     3 : s:=s+'N';
    end;
   end;
end;
s:=copy(s,1,A[1]);
ConvertFromByte:=s;
end;

Procedure ConvertInByte(S : String;Var A : SStr);
Var i,j   : byte;
    sb    : array[1..16]of byte;
begin
fillchar(sb,sizeof(sb),0);
fillchar(A,sizeof(A),0);
A[1]:=Length(S);
for i:=1 to length(s) do
   Case s[i] of
    'W' : sb[i]:=0;
    'E' : sb[i]:=1;
    'S' : sb[i]:=2;
    'N' : sb[i]:=3;
   end;
for i:=1 to 16 do begin
   j:=i mod 4;
   if j=0 then j:=4;
   A[(i+7) div 4]:=A[(i+7) div 4]+sb[i]*CAdd[j];
end;
end;

Function Can(i,j : integer) : boolean;
begin
Can:=(i>0)and(i<5)and(j>0)and(j<5);
end;

Function Can2(i,j,c : integer) : boolean;
begin
Can2:=(i>0)and(i<5)and(j>0)and(j<5)and(c<=N);
end;

Procedure FullSearch(I,J,CurI,CurJ,CurD,CurF,CurL : integer);
Var u,ul    : integer;
    P       : string[16];
   Procedure Go(dI,dJ : integer);
    begin
     if Not(Can(CurI+dI,CurJ+dJ)) then exit;
     if PSearch[CurI+dI,CurJ+dJ]=1 then exit;
     if dJ=1 then CurPath:=CurPath + 'E';
     if dJ=-1 then CurPath:=CurPath + 'W';
     if dI=1 then CurPath:=CurPath + 'S';
     if dI=-1 then CurPath:=CurPath + 'N';
     FullSearch(I,J,CurI+dI,CurJ+dJ,CurD+1,CurF+St[CurL].F
[CurI+dI,CurJ+dJ],CurL);
    end;
begin
P:=CurPath;
ul:=A3[CurL+1,I,J,2];
if ul>MaxD-CurD then ul:=MaxD-CurD;
for u:=A3[CurL+1,I,J,1] to ul do
   if A[u,CurL+1,I,J]<>-1 then
    if A[u+CurD,CurL,CurI,CurJ]<CurF+A[u,CurL+1,I,J] then begin
     A[u+CurD,CurL,CurI,CurJ]:=CurF+A[u,CurL+1,I,J];
     ConvertInByte(CurPath,Tmp);
     A2[u+CurD,CurL,CurI,CurJ]:=Tmp;
     if u+CurD<A3[CurL,CurI,CurJ,1] then A3[CurL,CurI,CurJ,1]:=u+CurD;
     if u+CurD>A3[CurL,CurI,CurJ,2] then A3[CurL,CurI,CurJ,2]:=u+CurD;
    end;
PSearch[CurI,CurJ]:=1;
   Go(-1,0); CurPath:=P;
   Go(1,0); CurPath:=P;
   Go(0,-1); CurPath:=P;
   Go(0,1); CurPath:=P;
PSearch[CurI,CurJ]:=0;
end;

Procedure Init;
Var m,k,i,j,p : integer;
begin
Read(N);
for k:=N downto 1 do begin
   for i:=1 to 4 do
    for j:=1 to 4 do
     Read(St[k].F[i,j]);
   for i:=1 to 4 do
    for j:=1 to 4 do
     Read(St[k].D[i,j]);
end;
Read(R,C);
for m:=0 to MaxD do
   for k:=1 to MaxN+1 do
    for i:=1 to 4 do
     for j:=1 to 4 do
      A[m,k,i,j]:=-1;
fillchar(A2,SizeOf(A2),0);
   for k:=1 to MaxN+1 do
    for i:=1 to 4 do
     for j:=1 to 4 do begin
      A3[k,i,j,1]:=255;
      A3[k,i,j,2]:=0;
     end;
A[0,N+1,R,C]:=0;
A3[N+1,R,C,1]:=0;
A3[N+1,R,C,2]:=0;
end;

Function RestorePath(ti,tj,td : integer) : string;
Var ci,cj,cd,cz,v : integer;
    Ans,S         : string[255];
begin
ci:=ti;
cj:=tj;
cd:=td;
cz:=1;
Ans:='';
While True do begin
    if cz=N+1 then break;
    if cz>1

Yessss! I get AC!!!!!!!!!!!!!!!!!!!!!! SmallInt isn't good.

Posted by Nazarov Denis (nsc2001@rambler.ru) 18 Feb 2002 16:53

> Program t1171;{$N+}
>
> Const MaxN = 16;
>        MaxD = 256;
>        CAdd : array[1..4]of byte=(1,4,16,64);
>
> Type Integer = SmallInt;
>       SStr    = array[1..5]of byte;
>       AStr    = array[1..2]of byte;
>       Floor   = array[1..4,1..4]of integer;
>       SFloor = array[1..4,1..4]of SStr;
>       AFloor = array[1..4,1..4]of AStr;
>
> Var   St          : array[1..MaxN]of record
>                       F : Floor;
>                       D : Floor;
>                     end;
>       A           : array[0..MaxD,1..MaxN+1]of Floor;
>       A2          : array[0..MaxD,1..MaxN+1]of SFloor;
>       A3          : array[1..MaxN+1]of SFloor;
>       CurPath     : String[16];
>       PSearch     : Floor;
>       Tmp         : SStr;
>       R,C,N       : integer;
>
> Function ConvertFromByte(A : SStr) : String;
> Var i,j,b,k : byte;
>     sb      : array[1..16]of byte;
>     s       : string[16];
> begin
>   s:='';
>   for j:=1 to 4 do begin
>    b:=A[j+1];
>    for i:=1 to 4 do begin
>     k:=b mod 4;
>     b:=b div 4;
>     Case k of
>      0 : s:=s+'W';
>      1 : s:=s+'E';
>      2 : s:=s+'S';
>      3 : s:=s+'N';
>     end;
>    end;
>   end;
>   s:=copy(s,1,A[1]);
>   ConvertFromByte:=s;
> end;
>
> Procedure ConvertInByte(S : String;Var A : SStr);
> Var i,j   : byte;
>     sb    : array[1..16]of byte;
> begin
>   fillchar(sb,sizeof(sb),0);
>   fillchar(A,sizeof(A),0);
>   A[1]:=Length(S);
>   for i:=1 to length(s) do
>    Case s[i] of
>     'W' : sb[i]:=0;
>     'E' : sb[i]:=1;
>     'S' : sb[i]:=2;
>     'N' : sb[i]:=3;
>    end;
>   for i:=1 to 16 do begin
>    j:=i mod 4;
>    if j=0 then j:=4;
>    A[(i+7) div 4]:=A[(i+7) div 4]+sb[i]*CAdd[j];
>   end;
> end;
>
> Function Can(i,j : integer) : boolean;
> begin
>   Can:=(i>0)and(i<5)and(j>0)and(j<5);
> end;
>
> Function Can2(i,j,c : integer) : boolean;
> begin
>   Can2:=(i>0)and(i<5)and(j>0)and(j<5)and(c<=N);
> end;
>
> Procedure FullSearch(I,J,CurI,CurJ,CurD,CurF,CurL : integer);
> Var u,ul    : integer;
>     P       : string[16];
>    Procedure Go(dI,dJ : integer);
>     begin
>      if Not(Can(CurI+dI,CurJ+dJ)) then exit;
>      if PSearch[CurI+dI,CurJ+dJ]=1 then exit;
>      if dJ=1 then CurPath:=CurPath + 'E';
>      if dJ=-1 then CurPath:=CurPath + 'W';
>      if dI=1 then CurPath:=CurPath + 'S';
>      if dI=-1 then CurPath:=CurPath + 'N';
>      FullSearch(I,J,CurI+dI,CurJ+dJ,CurD+1,CurF+St[CurL].F
> [CurI+dI,CurJ+dJ],CurL);
>     end;
> begin
>   P:=CurPath;
>   ul:=A3[CurL+1,I,J,2];
>   if ul>MaxD-CurD then ul:=MaxD-CurD;
>   for u:=A3[CurL+1,I,J,1] to ul do
>    if A[u,CurL+1,I,J]<>-1 then
>     if A[u+CurD,CurL,CurI,CurJ]<CurF+A[u,CurL+1,I,J] then begin
>      A[u+CurD,CurL,CurI,CurJ]:=CurF+A[u,CurL+1,I,J];
>      ConvertInByte(CurPath,Tmp);
>      A2[u+CurD,CurL,CurI,CurJ]:=Tmp;
>      if u+CurD<A3[CurL,CurI,CurJ,1] then A3
[CurL,CurI,CurJ,1]:=u+CurD;
>      if u+CurD>A3[CurL,CurI,CurJ,2] then A3
[CurL,CurI,CurJ,2]:=u+CurD;
>     end;
>   PSearch[CurI,CurJ]:=1;
>    Go(-1,0); Cur