program pku1088;
const max=100;
      dt:array[1..4,1..2] of integer=((-1,0),(1,0),(0,-1),(0,1));
var r,c,n,i,j,k,s,x,y:integer;
    t,map:array[0..max+1,0..max+1] of integer;
    tree:array[1..max*max,1..2] of integer;
 function min(x,y:integer):boolean;
 var mi:integer;
     mb:boolean;
 begin
    mb:=true;
    for mi:=1 to 4 do
       mb:=mb and ((map[x,y]<=map[x+dt[mi,1],y+dt[mi,2]])or(t[x+dt[mi,1],y+dt[mi,2]]>0));
    min:=mb;
 end;
begin
   while not seekeof(input) do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(t,sizeof(t),0);
      fillchar(tree,sizeof(tree),0);
      readln(r,c);
      for i:=1 to r do
      begin
         for j:=1 to c do read(map[i,j]);
         readln;
      end;
      for i:=0 to r+1 do
      begin
         map[i,0]:=maxint;
         map[i,c+1]:=maxint;
      end;
      for i:=0 to c+1 do
      begin
         map[0,i]:=maxint;
         map[r+1,i]:=maxint;
      end;
      n:=0;
      for i:=1 to r do
         for j:=1 to c do
            if (map[i,j]<=map[i-1,j])and(map[i,j]<=map[i+1,j])
            and(map[i,j]<=map[i,j-1])and(map[i,j]<=map[i,j+1])
             then begin
                     n:=n+1;
                     tree[n,1]:=i;
                     tree[n,2]:=j;
                     t[i,j]:=1;
                  end;
      s:=0;
      i:=1;
      repeat
         x:=tree[i,1];
         y:=tree[i,2];
         for j:=1 to 4 do
            if (0<x+dt[j,1])and(x+dt[j,1]<=r)
            and(0<y+dt[j,2])and(y+dt[j,2]<=c)
            and(t[x+dt[j,1],y+dt[j,2]]=0)and min(x+dt[j,1],y+dt[j,2])
             then begin
                     n:=n+1;
                     tree[n,1]:=x+dt[j,1];
                     tree[n,2]:=y+dt[j,2];
                     for k:=1 to 4 do
                        if (map[tree[n,1]+dt[k,1],tree[n,2]+dt[k,2]]<map[tree[n,1],tree[n,2]])
                         and (t[tree[n,1]+dt[k,1],tree[n,2]+dt[k,2]]+1>t[tree[n,1],tree[n,2]])
                         then t[tree[n,1],tree[n,2]]:=t[tree[n,1]+dt[k,1],tree[n,2]+dt[k,2]]+1;
                     if t[tree[n,1],tree[n,2]]>s then s:=t[tree[n,1],tree[n,2]];
                  end;
         i:=i+1;
      until i>n;
      writeln(s);
   end;
end.

• 能用广搜吗? (2407) xfxyjwf 2005-06-07 01:02:53
• 不是DP嘛。。。 (2407) js05 2005-06-07 09:13:12