讨论 / 谁能看看我的引水入城啊!!!
谧芒 2012-10-07 06:57:00
点我顶贴 收藏 删除
他只过六个点!!!!!!!!!!!!!!

program aa;

var

e:array[1..501,1..501] of longint;

a,b,c,d:array[1..500] of longint;

f:array[1..500] of boolean;

v:array[1..500] of integer;

i,j,k,n,m,x:longint;

sum,max,min:longint;

procedure sort(i,j:integer);

var

x,l,r,t:integer;

begin

l:=i;

r:=j;

x:=(l+r) div 2;

repeat

while a[l]<a[x] do inc(l);

while a[r]>a[x] do dec(r);

if l<=r then begin

t:=a[l];

a[l]:=a[r];

a[r]:=t;

t:=b[l];

b[l]:=b[r];

b[r]:=t;

inc(l);

dec(r);

end;

until l>r;

if i<r then sort(i,r);

if l<j then sort(l,j);

end;

procedure bfs(i,j:integer);

begin

if (i<=0) or (i>n) or (j<=0) or (j>m) then exit;

if i=n then

begin

if not f[j] then

begin

f[j]:=true; inc(sum);

end;

if j<min then min:=j;

if j>max then max:=j;

end;

if e[i-1,j]<e[i,j] then bfs(i-1,j);

if e[i,j-1]<e[i,j] then bfs(i,j-1);

if e[i+1,j]<e[i,j] then bfs(i+1,j);

if e[i,j+1]<e[i,j] then bfs(i,j+1);

end;

begin

fillchar(f,sizeof(f),false);

readln(n,m);

for i:=1 to n do

for j:=1 to m do

read(e[i,j]);

sum:=0;

for i:=1 to m do

begin

min:=501;

max:=0;

bfs(1,i);

if min<>501 then

a[i]:=min;

k:=i;

b[i]:=max;

if sum=m then break;

end;

if sum<m then begin writeln(0);writeln(m-sum);exit;end;

sort(1,k);

i:=1;

while a[i]=0 do

inc(i);

fillchar(v,sizeof(v),$1b);

v[0]:=0;

for j:=i to k do

for x:=a[j] to b[j] do

if v[a[j]-1]+1<v[x] then v[x]:=v[a[j]-1]+1;

writeln(1);

writeln(v[m]);

end.

#1 小小的wo@2012-09-14 05:53:00
回复 删除
还好
#2 谧芒@2012-10-07 06:47:00
回复 删除
还是自己来吧

program water;

var i,j,k,n,m,cannot,l,r:longint;

flag:boolean;

h:array[0..600,0..600]of longint;

v:array[0..600,0..600]of boolean;

flow:array[0..1000,0..2]of longint;

f:array[0..1000]of longint;

procedure floodfill(x,y:longint);

begin

if v[x,y] then exit;

v[x,y]:=true;

if h[x-1,y]<h[x,y] then floodfill(x-1,y);

if h[x+1,y]<h[x,y] then floodfill(x+1,y);

if h[x,y-1]<h[x,y] then floodfill(x,y-1);

if h[x,y+1]<h[x,y] then floodfill(x,y+1);

end;

procedure swap(var a,b:longint);

var t:longint;

begin

t:=a;a:=b;b:=t;

end;

function min(a,b:longint):longint;

begin

if a<b then exit(a) else exit(b);

end;

begin

readln(n,m);

fillchar(h,sizeof(h),127);

for i:=1 to n do

for j:=1 to m do

read(h[i,j]);

fillchar(v,sizeof(v),false);

for i:=1 to m do floodfill(1,i);

cannot:=0;

for i:=1 to m do

if not v[n,i] then inc(cannot);

if cannot<>0 then

begin

writeln(0);writeln(cannot);halt;

end;

writeln(1);

k:=0;

for i:=1 to m do

begin

fillchar(v,sizeof(v),false);

floodfill(1,i);

l:=0;r:=m+1;flag:=true;

while (l<=r)and(flag) do

begin

flag:=false;

if not v[n,l] then begin

inc(l);flag:=true;

end;

if not v[n,r] then begin

dec(r);flag:=true;

end;

end;

if l>r then continue;

inc(k);flow[k,1]:=l;flow[k,2]:=r;

end;

for i:=1 to k-1 do

for j:=i+1 to k do

if flow[i,1]>flow[j,1] then

begin

swap(flow[i,1],flow[j,1]);

swap(flow[i,2],flow[j,2]);

end;

fillchar(f,sizeof(f),127);f[0]:=0;

for i:=1 to k do

for j:=flow[i,1] to flow[i,2] do

f[j]:=min(f[j],f[flow[i,1]-1]+1);

writeln(f[m]);

end.

#3 谧芒@2012-10-07 06:57:00
回复 删除
回复 沙发小小的wo 的帖子

你 这也太扯了吧!!!!!!!!

查看更多回复
提交回复