比赛 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.