记录编号	133687	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	萧瑟风声	是否通过	通过
代码语言	Pascal	运行时间	0.976 s
提交时间	2014-10-28 18:32:31	内存使用	1.37 MiB

program wiki1066;
var
 a:array[0..501,0..501]of longint;
 f:array[0..501,0..501]of boolean;
 n,m,i,j,k,t,p,ans,max,s:longint;
 head,tail:array[1..500]of longint;
 ff:array[1..500]of boolean;

procedure dfs(x,y:longint);
begin
 if x=n then
  begin
  if y<head[k] then head[k]:=y;
  if y>tail[k] then tail[k]:=y;
  if not ff[y] then begin inc(p); ff[y]:=true; end;
  end;
 if not f[x,y] then begin f[x,y]:=true; end else exit;
 if a[x,y+1]<a[x,y] then dfs(x,y+1);
 if a[x,y-1]<a[x,y] then dfs(x,y-1);
 if a[x+1,y]<a[x,y] then dfs(x+1,y);
 if a[x-1,y]<a[x,y] then dfs(x-1,y);
end;

procedure qsort(h,t:longint);
var
 i,j,k,x:longint;
begin
 i:=h;
 j:=t;
 x:=head[(h+t) div 2];
 while (i<j) do
  begin
  while head[i]<x do inc(i);
  while head[j]>x do dec(j);
  if (i<=j) then
   begin
   k:=head[i];
   head[i]:=head[j];
   head[j]:=k;
   k:=tail[i];
   tail[i]:=tail[j];
   tail[j]:=k;
   inc(i);
   dec(j);
   end;
  end;
 if (i<t) then qsort(i,t);
 if (h<j) then qsort(h,j);
end;

begin
 assign(input,'flow.in');
 assign(output,'flow.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 fillchar(ff,sizeof(ff),0);
 fillchar(head,sizeof(head),127);
 fillchar(tail,sizeof(tail),0);
 fillchar(a,sizeof(a),127);
 for i:=1 to n do
  for j:=1 to m do
   read(a[i,j]);
 p:=0;
 for i:=1 to m do
  begin
   fillchar(f,sizeof(f),0);
   k:=i;
   dfs(1,i);
  end;
 if (p=m) then
	begin
	writeln(1);
	qsort(1,m);
	t:=1;
	s:=1;
	while (t<=m) do
	 begin
	 max:=0;
	 k:=0;
	 for i:=s to m do
	  if head[i]>t then begin s:=i; break; end
	  else
	  if tail[i]>max then
	   begin
	   max:=tail[i];
	   k:=i;
	   end;
	 inc(ans);
	 t:=max+1;
     end;
	writeln(ans);
	end;
 if (p<>m) then
 begin
  ans:=0;
  for i:=1 to m do
  if not ff[i] then inc(ans);
  writeln(0);
  writeln(ans);
 end;
 close(input);
 close(output);
end.