jiry_2's Blog

数据范围很小，用DFS来个时空复杂度都是n2m2t乱搞搞就A掉了

program p1295;
	const
		h:array[1..4] of longint=(1,0,-1,0);
		s:array[1..4] of longint=(0,1,0,-1);
	var
		pd1:array[1..30,1..30,1..30,1..30,0..30] of boolean;
		pd2:array[1..30,1..30,1..30,1..30] of boolean;
		bo:array[1..30,1..30] of boolean;
		n,m,i,j,ii,jj,t:longint;
		ch:char;
		max:extended;
	procedure dfs(k1,k2,k3,k4,k5:longint);
		var
			i,j,a,b:longint;
		begin
			pd2[k1,k2,k3,k4]:=true;
			pd1[k1,k2,k3,k4,k5]:=true;
			for i:=1 to 4 do begin
				a:=k3+h[i]; b:=k4+s[i];
				if (a>0) and (a<=n) and (b>0) and (b<=m) then begin
					if (bo[a,b]=false) and (k5+1<=t) and (pd1[k1,k2,a,b,k5+1]=false) then begin
						pd1[k1,k2,a,b,k5+1]:=true;
						dfs(k1,k2,a,b,k5+1);
					end else if (bo[a,b]=true) and (pd1[k1,k2,a,b,k5]=false) then begin
						pd1[k1,k2,a,b,k5]:=true;
						dfs(k1,k2,a,b,k5);
					end;
				end;
			end;
		end;
	begin
		readln(n,m,t);
		fillchar(bo,sizeof(bo),true);
		fillchar(pd1,sizeof(pd1),false);
		fillchar(pd2,sizeof(pd2),false);
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='1' then bo[i,j]:=false;
			end;
			readln;
		end;
		for i:=1 to n do
			for j:=1 to m do
				if bo[i,j]=true then
					dfs(i,j,i,j,0)
				else if t>0 then dfs(i,j,i,j,1);
		max:=0;
		for i:=1 to n do
			for j:=1 to m do
				for ii:=1 to n do
					for jj:=1 to m do
						if (pd2[i,j,ii,jj]) and (sqrt(sqr(i-ii)+sqr(j-jj))>max) then
							max:=sqrt(sqr(i-ii)+sqr(j-jj));
		writeln(max:0:6);
	end.