?? ac1171.pas
字號:
program ural1171;
const
maxn=16;
dir:array[0..3]of char=('E','S','W','N');
oppodir:array[0..3]of char=('W','N','E','S');
var
food,door:array[1..maxn,1..4,1..4]of byte;
dp:array[0..16{level},0..16*maxn{day},1..4,1..4]of word;
len:array[1..16,1..16*maxn,1..4,1..4]of byte;
path:array[1..16,1..16*maxn,1..4,1..4]of longint;
v:array[1..4,1..4]of boolean;
best:array[1..16,1..4,1..4]of word;
bpath:array[1..16,1..4,1..4]of longint;
n,x,y,l,i,j,got,d:word;
way:longint;
ratio:real;
s:string;
procedure updatebest(day:word;a,b:byte);
begin
if got>best[day,a,b] then begin
best[day,a,b]:=got;
bpath[day,a,b]:=way;
end;
end;
procedure search(day:word;a,b,d:byte);
begin
inc(got,food[l,a,b]);way:=way shl 2+d;v[a,b]:=true;
updatebest(day,a,b);
if (b<4) and not v[a,b+1] then search(day+1,a,b+1,0);
if (a<4) and not v[a+1,b] then search(day+1,a+1,b,1);
if (b>1) and not v[a,b-1] then search(day+1,a,b-1,2);
if (a>1) and not v[a-1,b] then search(day+1,a-1,b,3);
dec(got,food[l,a,b]);way:=way shr 2;v[a,b]:=false;
end;
procedure update;
var
a,b,d,day:word;
begin
for a:=1 to 4 do
for b:=1 to 4 do
for d:=1 to 16 do
for day:=l to 16*l do
if (day>=d) and ((l=1) or (dp[l-1,day-d,i,j]>0))
and (best[d,a,b]>0){This took me 6 days to debug!!!}
and (dp[l-1,day-d,i,j]+best[d,a,b]>dp[l,day,a,b]) then begin
dp[l,day,a,b]:=dp[l-1,day-d,i,j]+best[d,a,b];
len[l,day,a,b]:=d-1;
path[l,day,a,b]:=bpath[d,a,b];
end;
end;
procedure track(l:byte);
var
i:byte;
s:string;
procedure extract(l:byte;p:longint;var s:string);
var
i:byte;
begin
s:='';
for i:=1 to l do begin
s:=s+oppodir[p mod 4];
p:=p shr 2;
end;
end;
begin
extract(len[l,d,x,y],path[l,d,x,y],s);
write(s);
if l>1 then begin
for i:=1 to length(s) do
case s[i] of 'E':inc(y);'S':inc(x);'W':dec(y);'N':dec(x);end;
write('D');
dec(d,length(s)+1);
end
else
writeln;
end;
begin
read(n);
for l:=n downto 1 do begin
for i:=1 to 4 do
for j:=1 to 4 do
read(food[l,i,j]);
for i:=1 to 4 do
for j:=1 to 4 do
read(door[l,i,j]);
end;
read(x,y);
for i:=1 to 4 do
for j:=1 to 4 do
door[1,i,j]:=1;
for l:=1 to n do
for i:=1 to 4 do
for j:=1 to 4 do
if door[l,i,j]=1 then begin
fillchar(best,sizeof(best),0);
got:=0;way:=0;
search(1,i,j,0);
update;
end;
for i:=n to 16*n do
if dp[n,i,x,y]/i>ratio then begin
ratio:=dp[n,i,x,y]/i;
d:=i;
end;
writeln(ratio:0:4);
writeln(d-1);
for i:=n downto 1 do
track(i);
end.
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -