d1:array[1..4]of longint=(0,-1,0,1);
d2:array[1..4]of longint=(-1,0,1,0);
var
fill:array[0..501,0..501]of boolean;
a:array[0..501,0..501]of longint;
l,r:array[1..500,1..500]of longint;
pd:array[1..500]of boolean;
i,j,n,m,ans,max,maxi:longint;
procedure floodfill(x,y:longint); // 颜色填充
var
i:longint;
begin
if(x>n)or(x<1)or(y>m)or(y<1)then exit;
fill[x,y]:=false;
for i:=1 to 4 do
if fill[x+d1[i],y+d2[i]]and(a[x,y]>a[x+d1[i],y+d2[i]])then
floodfill(x+d1[i],y+d2[i]);
end;
procedure dfs(x,y:longint); // 记忆化搜索（深）
var
i,dx,dy:longint;
begin
fill[x,y]:=false;
if x=n then begin
if l[x,y]>y then
l[x,y]:=y;
if r[x,y]<y then
r[x,y]:=y;
end;
for i:=1 to 4 do begin
dx:=x+d1[i];
dy:=y+d2[i];
if(dx>n)or(dx<1)or(dy>m)or(dy<1)then continue;
if a[x,y]>a[dx,dy]then
if fill[dx,dy]then begin
dfs(dx,dy);
if l[x,y]>l[dx,dy]then
l[x,y]:=l[dx,dy];
if r[x,y]<r[dx,dy]then
r[x,y]:=r[dx,dy];
end else begin
if l[x,y]>l[dx,dy]then
l[x,y]:=l[dx,dy];
if r[x,y]<r[dx,dy]then
r[x,y]:=r[dx,dy];
end;
end;
end;
begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do
read(a[i,j]);
readln
end;
fillchar(fill,sizeof(fill),true);
for i:=1 to m do
if fill[1,i]then
floodfill(1,i);
ans:=0;
for i:=1 to m do
if fill[n,i]then inc(ans);
if ans>0 then begin
writeln('0');
writeln(ans);
readln;
halt;
end;
fillchar(fill,sizeof(fill),true);
fillchar(l,sizeof(l),$7f);
fillchar(r,sizeof(r),0);
for i:=1 to m do
if fill[1,i]then
dfs(1,i);
fillchar(pd,sizeof(pd),true);
ans:=0;
repeat
max:=0;
for i:=1 to m do begin
if l[1,i]>r[1,i]then pd[i]:=false;
if not pd[i]then continue;
if max<r[1,i]-l[1,i]+1 then begin
max:=r[1,i]-l[1,i]+1;
maxi:=i;
end;
end;
if max>0 then inc(ans);
pd[maxi]:=false;
for i:=1 to m do begin
if not pd[i]then continue;
if(l[1,i]>=l[1,maxi])and(l[1,i]<=r[1,maxi])then
l[1,i]:=r[1,maxi]+1;
if(r[1,i]>=l[1,maxi])and(r[1,i]<=r[1,maxi])then
r[1,i]:=l[1,maxi]-1;
end;
until max=0;
writeln('1');
writeln(ans);
readln;
end.
测试结果1: 通过本测试点|有效耗时219ms
测试结果2: 通过本测试点|有效耗时171ms
测试结果3: 通过本测试点|有效耗时532ms
测试结果4: 通过本测试点|有效耗时62ms
测试结果5: 通过本测试点|有效耗时172ms
测试结果6: 通过本测试点|有效耗时172ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时234ms
测试结果10: 测试结果错误.错误结果为:1
87
正确结果应为:1
86
//擦，为什么最后一个会比正确答案多一个？？？
type
cc=record
l,r:Longint;
end;
var
b:array[0..505,0..506]of cc;
i,j,k,m,n,cover:Longint;
a:array[0..505,0..505]of longint;
bo:array[0..505]of boolean;
bo1:array[0..505,0..505]of boolean;
function check(x,y,val:Longint):boolean;
var
i,j:Longint;
begin
if (x<1)or(x>n)or(y<1)or(y>m) then exit(false);
if a[x,y]<val then exit(true);
exit(false);
end;
procedure doit(k:cc;x,y:Longint);
var
i,j:Longint;
begin
if k.l=0 then exit;
if (b[x,y].l=0)or(b[x,y].l>k.l) then b[x,y].l:=k.l;
if b[x,y].r<k.r then b[x,y].r:=k.r;
end;
procedure flood(x,y:Longint);
var
i,j,k:Longint;
now:cc;
begin
if bo1[x,y] then exit;
bo1[x,y]:=true;
if x=n then
begin
bo[y]:=true;
now.l:=y;now.r:=y;
doit(now,x,y);
end;
if check(x+1,y,a[x,y]) then begin flood(x+1,y);doit(b[x+1,y],x,y); end;
if check(x-1,y,a[x,y]) then begin flood(x-1,y);doit(b[x-1,y],x,y); end;
if check(x,y-1,a[x,y]) then begin flood(x,y-1);doit(b[x,y-1],x,y); end;
if check(x,y+1,a[x,y]) then begin flood(x,y+1);doit(b[x,y+1],x,y); end;
end;
procedure step1;
var
k:cc;
begin
fillchar(bo,sizeof(bo),false);
cover:=0;
for i:=1 to m do
flood(1,i);
for i:=1 to m do
if not bo[i] then
inc(cover);
if cover<>0 then
begin
writeln(0);
writeln(cover);
halt;
end;
end;
procedure init;
var
i,j:Longint;
begin
fillchar(b,sizeof(b),0);
fillchar(bo1,sizeof(bo1),false);
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure step2;////我的都是贪心`~~
var
i,j,k,now,note,ans,start:Longint;
begin
now:=0;
note:=1;
ans:=0;
while now<m do
begin
inc(ans);
start:=now;
for i:=note to m do
if (b[1,i].l=0)then
continue
else
if (b[1,i].l-1<=start) then
if b[1,i].r>now then now:=b[1,i].r
else
else
begin
note:=i;
break;
end;
end;
writeln(1);
writelN(ans);
end;
begin
init;
step1;
step2;
end.