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 1145. Rope in the Labyrinth

I get TL. I've worked hard at my algorithm, but I still was getting WA. Can anybody help me to optimize my program, please(+)
Posted by Nazarov Denis (nsc2001@rambler.ru) 29 Jan 2002 20:22
My code:

{$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
Program t1145;

Const MaxN  = 1000;
      MaxPL = 1500;
      Cadd  : array[1..4]of byte=
              (1, 4, 16, 64);

Type  Integer=SmallInt;
      PList = record
       P   : array[1..MaxPL,1..3] of integer;
       Len : integer;
      end;

Var   Map       : array[1..MaxN,1..MaxN div 4]of byte;
                  {value of
                   '0' : forbidden
                   '1' : free
                   '2' : first view
                   '3' : last view  }
      N,M,i,j   : integer;
      Idiv4     : array[1..MaxN]of integer;
      Imod4     : array[1..MaxN]of integer;
      CAmod     : array[0..255,1..4]of byte;
      CAdiv     : array[0..255,1..4]of byte;
      Hmul      : array[0..4,1..4]of byte;
      Pred,New  : PList;
      ch        : char;
      CurLen    : integer;
      Ex        : boolean;

Function GetValue(i,j : integer) : byte;
Var Fj,Sj  : integer;
    Pvalue : byte;
    k,l,h  : byte;
 begin
  Fj:=Idiv4[j]+1;
  if Imod4[j]=0 then Fj:=Fj-1;
  Sj:=Imod4[j];
  if Sj=0 then Sj:=4;
  l:=Map[i,Fj];
  Pvalue:=0;
  for k:=4 downto 1 do begin
    h:=CAdiv[l,k];
    l:=CAmod[l,k];
    if Sj=k then begin
     Pvalue:=h;
     break;
    end;
   end;
  GetValue:=Pvalue;
 end;

Procedure SetValue(i,j : integer; value : byte);
Var Fj,Sj  : integer;
    Cvalue : byte;
    Pvalue : byte;
    k,l,h  : byte;
 begin
  Fj:=Idiv4[j]+1;
  if Imod4[j]=0 then Fj:=Fj-1;
  Sj:=Imod4[j];
  if Sj=0 then Sj:=4;
  l:=Map[i,Fj];
  Pvalue:=0;
  for k:=4 downto 1 do begin
    h:=CAdiv[l,k];
    l:=CAmod[l,k];
    if Sj<>k then Pvalue:=Pvalue+Hmul[h,k];
   end;
  Cvalue:=Hmul[value,Sj];
  Map[i,Fj]:=Pvalue+Cvalue;
 end;

Procedure Anlysis(x,y : integer; CurValue,Tr : byte);
 begin
  if (x<1)or(x>N)or(y<1)or(y>M) then exit;
  if GetValue(x,y)<>CurValue-1 then exit;
  SetValue(x,y,CurValue);
  New.Len:=New.Len+1;
  New.P[New.Len,1]:=x;
  New.P[New.Len,2]:=y;
  New.P[New.Len,3]:=Tr;
  Ex:=false;
 end;

begin
 FillChar(Map,SizeOf(Map),0);
 For i:=1 to MaxN do Idiv4[i]:=i div 4;
 For i:=1 to MaxN do Imod4[i]:=i mod 4;
 For i:=0 to 255 do
  For j:=1 to 4 do
   CAdiv[i,j]:=i div Cadd[j];
 For i:=0 to 255 do
  For j:=1 to 4 do
   CAmod[i,j]:=i mod Cadd[j];
 For i:=0 to 3 do
  For j:=1 to 4 do
   Hmul[i,j]:=i*Cadd[j];
 Read(M,N);
 for i:=1 to N do
  for j:=1 to M do begin
    Read(ch);
    While (ch<>'.')and(ch<>'#') do Read(Ch);
    Case Ch of
     '.' : SetValue(i,j,1);
     '#' : SetValue(i,j,0);
    end;
   end;
 New.Len:=0;
 for i:=1 to N do begin
  for j:=1 to M do
   if GetValue(i,j)=1 then begin
     New.Len:=1;
     New.P[1,1]:=i;
     New.P[1,2]:=j;
     New.P[1,3]:=0;
     SetValue(i,j,2);
     break;
    end;
  if New.Len=1 then break;
 end;
 Repeat
  Ex:=true;
  Pred:=New;
  New.Len:=0;
  for i:=1 to Pred.Len do begin
    if Pred.P[i,3]<>1 then Anlysis(Pred.P[i,1]-1,Pred.P[i,2]  ,2,2);
    if Pred.P[i,3]<>2 then Anlysis(Pred.P[i,1]+1,Pred.P[i,2]  ,2,1);
    if Pred.P[i,3]<>3 then Anlysis(Pred.P[i,1]  ,Pred.P[i,2]-1,2,4);
    if Pred.P[i,3]<>4 then Anlysis(Pred.P[i,1]  ,Pred.P[i,2]+1,2,3);
   end;
 Until Ex;
 New:=Pred;
 New.Len:=1;
 New.P[1,3]:=0;
 CurLen:=-1;
 Repeat
  Ex:=true;
  CurLen:=CurLen+1;
  Pred:=New;
  New.Len:=0;
  for i:=1 to Pred.Len do begin
    if Pred.P[i,3]<>1 then Anlysis(Pred.P[i,1]-1,Pred.P[i,2]  ,3,2);
    if Pred.P[i,3]<>2 then Anlysis(Pred.P[i,1]+1,Pred.P[i,2]  ,3,1);
    if Pred.P[i,3]<>3 then Anlysis(Pred.P[i,1]  ,Pred.P[i,2]-1,3,4);
    if Pred.P[i,3]<>4 then Anlysis(Pred.P[i,1]  ,Pred.P[i,2]+1,3,3);
   end;
 Until Ex;
 Writeln(CurLen);
end.
Yessss! I get AC!!!!!!!!!!!!!!!!!!!!!! TL was only of Delphi compiler.
Posted by Nazarov Denis (nsc2001@rambler.ru) 29 Jan 2002 20:45
> My code:
>
> {$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-}
> Program t1145;
>
> Const MaxN  = 1000;
>       MaxPL = 1500;
>       Cadd  : array[1..4]of byte=
>               (1, 4, 16, 64);
>
> Type  Integer=SmallInt;
>       PList = record
>        P   : array[1..MaxPL,1..3] of integer;
>        Len : integer;
>       end;
>
> Var   Map       : array[1..MaxN,1..MaxN div 4]of byte;
>                   {value of
>                    '0' : forbidden
>                    '1' : free
>                    '2' : first view
>                    '3' : last view  }
>       N,M,i,j   : integer;
>       Idiv4     : array[1..MaxN]of integer;
>       Imod4     : array[1..MaxN]of integer;
>       CAmod     : array[0..255,1..4]of byte;
>       CAdiv     : array[0..255,1..4]of byte;
>       Hmul      : array[0..4,1..4]of byte;
>       Pred,New  : PList;
>       ch        : char;
>       CurLen    : integer;
>       Ex        : boolean;
>
> Function GetValue(i,j : integer) : byte;
> Var Fj,Sj  : integer;
>     Pvalue : byte;
>     k,l,h  : byte;
>  begin
>   Fj:=Idiv4[j]+1;
>   if Imod4[j]=0 then Fj:=Fj-1;
>   Sj:=Imod4[j];
>   if Sj=0 then Sj:=4;
>   l:=Map[i,Fj];
>   Pvalue:=0;
>   for k:=4 downto 1 do begin
>     h:=CAdiv[l,k];
>     l:=CAmod[l,k];
>     if Sj=k then begin
>      Pvalue:=h;
>      break;
>     end;
>    end;
>   GetValue:=Pvalue;
>  end;
>
> Procedure SetValue(i,j : integer; value : byte);
> Var Fj,Sj  : integer;
>     Cvalue : byte;
>     Pvalue : byte;
>     k,l,h  : byte;
>  begin
>   Fj:=Idiv4[j]+1;
>   if Imod4[j]=0 then Fj:=Fj-1;
>   Sj:=Imod4[j];
>   if Sj=0 then Sj:=4;
>   l:=Map[i,Fj];
>   Pvalue:=0;
>   for k:=4 downto 1 do begin
>     h:=CAdiv[l,k];
>     l:=CAmod[l,k];
>     if Sj<>k then Pvalue:=Pvalue+Hmul[h,k];
>    end;
>   Cvalue:=Hmul[value,Sj];
>   Map[i,Fj]:=Pvalue+Cvalue;
>  end;
>
> Procedure Anlysis(x,y : integer; CurValue,Tr : byte);
>  begin
>   if (x<1)or(x>N)or(y<1)or(y>M) then exit;
>   if GetValue(x,y)<>CurValue-1 then exit;
>   SetValue(x,y,CurValue);
>   New.Len:=New.Len+1;
>   New.P[New.Len,1]:=x;
>   New.P[New.Len,2]:=y;
>   New.P[New.Len,3]:=Tr;
>   Ex:=false;
>  end;
>
> begin
>  FillChar(Map,SizeOf(Map),0);
>  For i:=1 to MaxN do Idiv4[i]:=i div 4;
>  For i:=1 to MaxN do Imod4[i]:=i mod 4;
>  For i:=0 to 255 do
>   For j:=1 to 4 do
>    CAdiv[i,j]:=i div Cadd[j];
>  For i:=0 to 255 do
>   For j:=1 to 4 do
>    CAmod[i,j]:=i mod Cadd[j];
>  For i:=0 to 3 do
>   For j:=1 to 4 do
>    Hmul[i,j]:=i*Cadd[j];
>  Read(M,N);
>  for i:=1 to N do
>   for j:=1 to M do begin
>     Read(ch);
>     While (ch<>'.')and(ch<>'#') do Read(Ch);
>     Case Ch of
>      '.' : SetValue(i,j,1);
>      '#' : SetValue(i,j,0);
>     end;
>    end;
>  New.Len:=0;
>  for i:=1 to N do begin
>   for j:=1 to M do
>    if GetValue(i,j)=1 then begin
>      New.Len:=1;
>      New.P[1,1]:=i;
>      New.P[1,2]:=j;
>      New.P[1,3]:=0;
>      SetValue(i,j,2);
>      break;
&am