极类似动归的广搜？反正各种算法傻傻分不清…写之前叹了一句，好久不写广搜了啊！呵呵真的写了好久，大约一个钟头？
f[i,j,0]表示到点(i,j)且最后一步为下降的最少步数，f[i,j,1]就是上升。莫名让我想到了NOIP2013的摆花，那时我也脑坏地写了个O(N^2)也是这样[1..n,1..n,0..1]的数组…
犯的错误就是由于判断更高之后要入队列，判断更低之后也要入队列，否则有可能前面的true被后面的false给搞掉…这就是为什么我过了三个数据，剩下的数据都只错了一两行的原因。（数据真弱=。=）
90行+广搜，有种hold不住的感觉。今天上课听了树链剖分我表示…那种题遇到了干脆就送掉吧…=y=能搞懂LCA就是万幸了。
program mr440;
const dx:array[..] of integer=(,,-,);
dy:array[..] of integer=(,-,,);
var map:array[..,..] of integer;
mark:array[..,..] of boolean;
m,n,i,j,l,r,tx,ty:longint;
f:array[..,..,..] of longint;
lx,ly:array[..] of integer;
flag:boolean; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function min3(a,b,c:longint):longint;
begin
if (a<b) and (a<c) then exit(a);
if (b<c) and (b<a) then exit(b);
exit(c);
end; begin
assign(input,'mr440.in2');reset(input);
assign(output,'mr440.ou2');rewrite(output);
readln(m,n);
for i:= to m do
begin
for j:= to n do
read(map[i,j]);
readln;
end;
fillchar(mark,sizeof(mark),);
fillchar(f,sizeof(f),$7f);
l:=;r:=;lx[l]:=;ly[l]:=;mark[,]:=true;f[,,]:=;f[,,]:=;
while (l<=r) do
begin
for i:= to do
begin
tx:=lx[l]+dx[i];
ty:=ly[l]+dy[i];
if (tx<) or (tx>m+) or (ty<) or (ty>n+) then continue;
if map[tx,ty]>=map[lx[l],ly[l]] then {1 shangsheng}
begin
flag:=false;
if f[lx[l],ly[l],]<f[tx,ty,] then
begin
f[tx,ty,]:=f[lx[l],ly[l],];
flag:=true;
end;
if f[lx[l],ly[l],]+<f[tx,ty,] then
begin
f[tx,ty,]:=f[lx[l],ly[l],]+;
flag:=true;
end;
if (mark[tx,ty]=false) and (flag=true) then
begin
inc(r);
lx[r]:=tx;ly[r]:=ty;
mark[tx,ty]:=true;
end;
end;
if map[tx,ty]<=map[lx[l],ly[l]] then
begin
flag:=false;
if f[lx[l],ly[l],]<f[tx,ty,] then
begin
f[tx,ty,]:=f[lx[l],ly[l],];
flag:=true;
end;
if f[lx[l],ly[l],]+<f[tx,ty,] then
begin
f[tx,ty,]:=f[lx[l],ly[l],]+;
flag:=true;
end;
if (mark[tx,ty]=false) and (flag=true) then
begin
inc(r);
lx[r]:=tx;ly[r]:=ty;
mark[tx,ty]:=true;
end;
end;
end;
mark[lx[l],ly[l]]:=false;
inc(l);
end;
for i:= to m do
begin
write(min(f[i,,]+f[i,,],min(f[i,,],f[i,,])*+),' ');
for j:= to n do
write(min(f[i,j,]+f[i,j,],min(f[i,j,],f[i,j,])*+),' ');
writeln;
end;
close(input);close(output);
end.
崎岖的山区