Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不是DP嘛。。。

Posted by js05 at 2005-06-07 09:13:12 on Problem 1088
In Reply To:我是用广度做的,为什么会WA啊? Posted by:15pengyi at 2005-06-07 00:56:04
> 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.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator