ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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;
(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;
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
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
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
For i:=0 to 255 do
For j:=1 to 4 do
For i:=0 to 3 do
For j:=1 to 4 do
for i:=1 to N do
for j:=1 to M do begin
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;
>               (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;
>       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
>     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
>     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
>  For i:=0 to 255 do
>   For j:=1 to 4 do
>  For i:=0 to 3 do
>   For j:=1 to 4 do
>  for i:=1 to N do
>   for j:=1 to M do begin
>     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