| ENG RUS | Timus Online Judge |
Обсуждение задачи 1145. Нить в лабиринте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(+) Послано Nazarov Denis (nsc2001@rambler.ru) 29 янв 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. Послано Nazarov Denis (nsc2001@rambler.ru) 29 янв 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 |