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

help!!! WHY MLE!!!
Posted by TOHA-B 9 Jul 2004 15:50
Somebody!! help!! why mle

label 1;
type
coor=record
x,y:integer;
end;
var
a,b:array [0..1001,0..1001] of boolean;
i,j:integer;
n,m,xc,yc:integer;
k1,k2,k:longint;
s:string;
c,d:array [1..4000] of coor;

begin
fillchar(a,sizeof(a),false);
for i:=1 to n do begin
for j:=1 to m do
if s[j]='#' then a[i,j]:=false else a[i,j]:=true;
end;
b:=a;

xc:=1001;
yc:=1001;
for i:=1 to n do
for j:=1 to n do
if a[i,j]=true then begin
xc:=i;
yc:=j;
goto 1;
end;
1:
if xc=1001 then begin
writeln(0);
halt;
end;

a[xc,yc]:=false;
k1:=1;
c[1].x:=xc;
c[1].y:=yc;
repeat
k2:=0;
for i:=1 to k1 do begin
if a[c[i].x+1,c[i].y] then begin
inc(k2);
d[k2].x:=c[i].x+1;
d[k2].y:=c[i].y;
a[c[i].x+1,c[i].y]:=false;
end;

if a[c[i].x,c[i].y+1] then begin
inc(k2);
d[k2].x:=c[i].x;
d[k2].y:=c[i].y+1;
a[c[i].x,c[i].y+1]:=false;
end;

if a[c[i].x-1,c[i].y] then begin
inc(k2);
d[k2].x:=c[i].x-1;
d[k2].y:=c[i].y;
a[c[i].x-1,c[i].y]:=false;
end;

if a[c[i].x,c[i].y-1] then begin
inc(k2);
d[k2].x:=c[i].x;
d[k2].y:=c[i].y-1;
a[c[i].x,c[i].y-1]:=false;
end;

end;

if k2=0 then break;
k1:=k2;
c:=d;
until false;

a:=b;
xc:=c[1].x;
yc:=c[1].y;
k:=0;

a[xc,yc]:=false;
k1:=1;
c[1].x:=xc;
c[1].y:=yc;
repeat
k2:=0;
for i:=1 to k1 do begin
if a[c[i].x+1,c[i].y] then begin
inc(k2);
d[k2].x:=c[i].x+1;
d[k2].y:=c[i].y;
a[c[i].x+1,c[i].y]:=false;
end;

if a[c[i].x,c[i].y+1] then begin
inc(k2);
d[k2].x:=c[i].x;
d[k2].y:=c[i].y+1;
a[c[i].x,c[i].y+1]:=false;
end;

if a[c[i].x-1,c[i].y] then begin
inc(k2);
d[k2].x:=c[i].x-1;
d[k2].y:=c[i].y;
a[c[i].x-1,c[i].y]:=false;
end;

if a[c[i].x,c[i].y-1] then begin
inc(k2);
d[k2].x:=c[i].x;
d[k2].y:=c[i].y-1;
a[c[i].x,c[i].y-1]:=false;
end;

end;

if k2=0 then break;
inc(k);
k1:=k2;
c:=d;
until false;
writeln(k);
end.
Re: help!!! WHY MLE!!!
Posted by Saturn 9 Jul 2004 21:44
Your program used two arrays 1001x1001=>Data size>2000KB=>MLE
Re: help!!! WHY MLE!!!
Posted by vano_B1 9 Jul 2004 22:05
But it is boolean

>a,b:array [0..1001,0..1001] of boolean;
Re: help!!! WHY MLE!!!
Posted by Saturn 9 Jul 2004 22:51
Boolean type is stored as a byte.
>Boolean 1 byte
>ByteBool 1 byte
>Wordbool 2 bytes
>Longbool 4 bytes
You can easily  found this info in FreePascal help.
Re: help!!! WHY MLE!!!
Posted by vano_B1 9 Jul 2004 23:47
ha.
I Thought boolean is 1/8 byte.
Thank you
well, how to save this labirint if array [1..1000,1..1000]>1000000 byte
Posted by vano_B1 9 Jul 2004 23:56
Re: well, how to save this labirint if array [1..1000,1..1000]>1000000 byte
Posted by Saturn 10 Jul 2004 13:05
You should use bits (1/8 byte) to store this array so
you will need only 1000000/8 bytes per array

Edited by author 10.07.2004 14:55
HOW? what type is it?
Posted by vano_B1 10 Jul 2004 16:06
Re: HOW? what type is it?
Posted by Saturn 10 Jul 2004 20:04
Pascal doesn't have type which uses less than 1 byte
but you can store bits by : shl,shr,or,and,xor,not...
Thank you.
Posted by vano_B1 10 Jul 2004 21:33
Re: HOW?
Posted by +FAMAS+ 26 Aug 2005 17:33
>Pascal doesn't have type which uses less than 1 byte
>but you can store bits by : shl,shr,or,and,xor,not...

Who can explain as it to make?
I use 2 array [1..1000,1..1000] but ML