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

where is wa?

Posted by 372284362 at 2010-04-21 14:34:19 on Problem 1088
program Project1;
type rec=record
       ii,jj:longint;
end;
const dx:array[1..4] of longint=(0,0,-1,1);
      dy:array[1..4] of longint=(1,-1,0,0);
var vis:array[1..100,1..100] of boolean;
    f,data:array[1..100,1..100] of longint;
    list:array[0..10000] of rec;
    i,j,k,n,m,tmp,ans:longint;
function checkn(x:longint):boolean;
begin
  if x<=0 then exit(false);
  if x>n then exit(false);
  exit(true);
end;
function checkm(x:longint):boolean;
begin
  if x<=0 then exit(false);
  if x>m then exit(false);
  exit(true);
end;
procedure qsort(s,t:longint);
var key,tt,l,r:longint;
begin
  tt:=random(t-s+1)+s;
  l:=s; r:=t;
  key:=data[list[tt].ii,list[tt].jj];
  while l<=r do
    begin
      while data[list[l].ii,list[l].jj]<key do inc(l);
      while data[list[r].ii,list[r].jj]>key do dec(r);
      if l<=r then
        begin
          list[0]:=list[l];
          list[l]:=list[r];
          list[r]:=list[0];
          inc(l); dec(r);
        end;
    end;
  if s<r then qsort(s,r);
  if l<t then qsort(l,t);
end;
procedure dfs(i,j:longint);
var k,tmp,x,y:longint;
begin
  vis[i,j]:=true;
  tmp:=0;
  for k:=1 to 4 do
    begin
      x:=i+dx[k];   y:=j+dy[k];
      if checkn(x) and checkm(y) and (data[i,j]<data[x,y]) then
        begin
          if not vis[x,y] then dfs(x,y);
          if f[x,y]>tmp then tmp:=f[x,y];
        end;
   end;
  inc(f[i,j],tmp);
end;
begin
  assign(input,'a.txt');
  reset(input);
  assign(output,'b.txt');
  rewrite(output);
  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(data[i,j]);
        tmp:=(i-1)*n+j;
        list[tmp].ii:=i;
        list[tmp].jj:=j;
      end;
  randomize;
  qsort(1,n*m);
  fillchar(vis,sizeof(vis),0);
  filldword(f,sizeof(f) shr 2,1);
  ans:=1;
  for k:=1 to n*m do
    begin
      i:=list[k].ii;
      j:=list[k].jj;
      if vis[i,j] then continue;
      dfs(i,j);
      if f[i,j]>ans then ans:=f[i,j];
    end;
  writeln(ans);
  close(input);
  close(output);
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