比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 zgyzhaoguangyang 运行时间 9.003 s
代码语言 Pascal 内存使用 3.56 MiB
提交时间 2014-04-18 09:15:33
显示代码纯文本
var a:array[-5..505,-5..505] of longint;
	q:array[0..250005,1..2] of longint;
        vv,v:array[-5..505,-5..505] of boolean;
	ans:qword;
	n,m,t:longint;
    z,c:array[1..4] of longint;
procedure init;
var i,j,x:longint;
begin
   readln(n,m,t);
    for i:=1 to n do
	  begin
	      for j:=1 to m do
		   read(a[i,j]);
		   readln;
	  end;
	  fillchar(vv,sizeof(vv),0);
	 for i:=1 to n do
	    begin
		   for j:=1 to m do
		     begin
			     read(x);
				 if x=1 then vv[i,j]:=true;
			 end;
			 readln;
		end;
   z[1]:=-1;z[2]:=0;z[3]:=0;z[4]:=1;
   c[1]:=0;c[2]:=-1;c[3]:=1;c[4]:=0;
end;

function ok(w,x,y:longint):boolean;
var i,j,head,tail,xx,yy,x1,y1:longint;
begin
   head:=1;tail:=1;
   fillchar(v,sizeof(v),1);
    q[1,1]:=x;q[1,2]:=y;
	v[x,y]:=false;
	while head<=tail do
	  begin
	      xx:=q[head,1];yy:=q[head,2];inc(head);
		  for i:=1 to 4 do
		    begin
			 x1:=xx+z[i];y1:=yy+c[i];
			 if (v[x1,y1]) and (x1>0) and (x1<=n) and (y1>0) and (y1<=m) and(abs(a[xx,yy]-a[x1,y1])<=w) then
			   begin
			     inc(tail);
				 if tail=t then exit(true);
				 q[tail,1]:=x1;q[tail,2]:=y1;
				v[x1,y1]:=false;
			   end;
			end;
	  end;
  exit(false);
end;

function find(l,r,x,y:longint):longint;
var mid:longint;
begin
    while l<r-1 do
	      begin
		     mid:=(l+r)>>1;
			 if ok(mid,x,y) then r:=mid
							  else l:=mid+1;
		  end;
    if ok(l,x,y) then exit(l);
	exit(r);
end;

procedure main;
var i,j:longint;
   temp:qword;
begin
   ans:=0;
    for i:=1 to n do
	  for j:=1 to m do
	  if vv[i,j] then
	    begin
		   temp:=find(0,1000000000,i,j);
		   inc(ans,temp);
		end;
	writeln(ans);
end;

begin
   assign(input,'skilevel.in');reset(input);
   assign(output,'skilevel.out');rewrite(output);
    init;main;
   close(input);close(output);
end.