比赛 |
20120712 |
评测结果 |
WWAAWWWAAA |
题目名称 |
登山 |
最终得分 |
50 |
用户昵称 |
fuhao |
运行时间 |
0.017 s |
代码语言 |
Pascal |
内存使用 |
70.68 MiB |
提交时间 |
2012-07-12 11:16:15 |
显示代码纯文本
program Hike;
const maxn=61; maxm=61;
dx:array[1..4] of longint=(1,0,-1,0);
dy:array[1..4] of longint=(0,1,0,-1);
var
f:array[0..maxn,0..maxm,0..maxn,0..maxm] of longint;
v:array[0..maxn,0..maxm] of boolean;
vv:array[0..maxn,0..maxm,0..maxn,0..maxm] of boolean;
step,h:array[0..maxn,0..maxm] of longint;
xx,yy:array[0..maxn*maxm] of longint;
distance,n,m,i,j,sx,sy:longint;
procedure floodfill(x,y:longint);
var i,hh,t:longint;
begin
hh:=0; t:=1; fillchar(v,sizeof(v),#0);
v[x,y]:=true; xx[1]:=x; yy[1]:=y; step[x,y]:=0;
repeat
inc(hh);
if (step[xx[hh],yy[hh]]>distance) or (h[x,y]>h[sx,sy])
and (step[xx[hh],yy[hh]]=distance) then
begin
distance:=step[xx[hh],yy[hh]];
sx:=x; sy:=y;
end;
for i:=1 to 4 do
if (xx[hh]+dx[i]>0) and (xx[hh]+dx[i]<=n) and
(yy[hh]+dy[i]>0) and (yy[hh]+dy[i]<=m) and
(h[xx[hh],yy[hh]]>h[xx[hh]+dx[i],yy[hh]+dy[i]]) and
(not v[xx[hh]+dx[i],yy[hh]+dy[i]]) then
begin
v[xx[hh]+dx[i],yy[hh]+dy[i]]:=true;
step[xx[hh]+dx[i],yy[hh]+dy[i]]:=step[xx[hh],yy[hh]]+1;
inc(t); xx[t]:=xx[hh]+dx[i]; yy[t]:=yy[hh]+dy[i];
end;
until hh>=t;
end;
procedure dp(x1,y1,x2,y2:longint);
var i,t:longint;
begin
if vv[x1,y1,x2,y2] then exit;
vv[x1,y1,x2,y2]:=true;
t:=0;
for i:=1 to 4 do
if (x1+dx[i]>0) and (x1+dx[i]<=n) and
(y1+dy[i]>0) and (y1+dy[i]<=m) and
(h[x1,y1]>h[x1+dx[i],y1+dy[i]]) and
(not v[x1+dx[i],y1+dy[i]]) and
((y1+dy[i]<>y2) or (x1+dx[i]<>x2)) then
begin
if not vv[x1+dx[i],y1+dy[i],x2,y2] then
begin
v[x1+dx[i],y1+dy[i]]:=true;
dp(x1+dx[i],y1+dy[i],x2,y2);
v[x1+dx[i],y1+dy[i]]:=false;
end;
if f[x1+dx[i],y1+dy[i],x2,y2]>t then
t:=f[x1+dx[i],y1+dy[i],x2,y2];
end;
for i:=1 to 4 do
if (x2+dx[i]>0) and (x2+dx[i]<=n) and
(y2+dy[i]>0) and (y2+dy[i]<=m) and
(h[x2,y2]>h[x2+dx[i],y2+dy[i]]) and
(not v[x2+dx[i],y2+dy[i]]) and
((y2+dy[i]<>y1) or (x2+dx[i]<>x1)) then
begin
if not vv[x1,y1,x2+dx[i],y2+dy[i]] then
begin
v[x2+dx[i],y2+dy[i]]:=true;
dp(x1,y1,x2+dx[i],y2+dy[i]);
v[x2+dx[i],y2+dy[i]]:=false;
end;
if f[x1,y1,x2+dx[i],y2+dy[i]]>t then
t:=f[x1,y1,x2+dx[i],y2+dy[i]];
end;
f[x1,y1,x2,y2]:=t+1;
end;
begin
assign(input,'hike.in'); reset(input);
assign(output,'hike.out'); rewrite(output);
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(h[i,j]);
for i:=1 to n do
for j:=1 to m do
if not v[i,j] then floodfill(i,j);
fillchar(v,sizeof(v),#0);
if (sx<>0) and (sy<>0) then dp(sx,sy,sx,sy);
writeln(f[sx,sy,sx,sy]);
close(input); close(output);
end.