blank.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program blank(input,output);
var g:array[1..1024,1..1024]of boolean;
    n:integer;

procedure init;
var k,be,en:integer;
begin
  assign(input,'blank.in');
  assign(output,'blank.out');
  reset(input);
  rewrite(output);
  readln(k);
  n:=2**k;
  fillchar(g,sizeof(g),true);
  readln(be,en);
  g[be,en]:=false
end;

function find(x1,y1,x2,y2:integer):integer;{寻找当前子问题中已被覆盖的点}
var i,t:integer;
begin
  for i:=x1 to (x2+x1)div 2 do
    for t:=y1 to (y2+y1)div 2 do
      if not g[i,t] then exit(1)
      else if not g[x2-i+1,t] then exit(3)
           else  if not g[i,y2-t+1] then exit(2)
                 else if not g[x2-i+1,y2-t+1] then exit(4)
end;

procedure work(x1,y1,x2,y2:integer);{分治递归求解，从（x1,y1）到（x2,y2）}
var  typ,i,t:integer;
begin
  if x2-x1=1 then  {当前已缩小为最简问题}
    begin
      typ:=0;  {表示该使用的地毯类型}
      for i:=x1 to x2 do
        for t:=y1 to y2 do
          begin
            inc(typ);
            if not g[i,t] then  {此坐标点被覆盖}
              case typ of	{输出}
	            	1:writeln(x2,' ',y2,' ',typ);
                2:writeln(x2,' ',y1,' ',typ);
		        3:writeln(x1,' ',y2,' ',typ);
		        4:writeln(x1,' ',y1,' ',typ)
              end
          end
    end
  else    {递归分治}
    begin
      typ:=find(x1,y1,x2,y2);{通过寻找已被覆盖的点求出此时使用的地毯类型}
      case typ of
            1:begin
	      	    g[(x1+x2)div 2+1,(y1+y2)div 2+1]:=false;
	      	    g[(x1+x2)div 2,(y1+y2)div 2+1]:=false;
	      	    g[(x1+x2)div 2+1,(y1+y2)div 2]:=false;
	      	    writeln((x1+x2)div 2+1,' ',(y1+y2)div 2+1,' ',1)
              end;
            2:begin
	            g[(x1+x2)div 2+1,(y1+y2)div 2]:=false;
		        g[(x1+x2)div 2,(y1+y2)div 2]:=false;
		        g[(x1+x2)div 2+1,(y1+y2)div 2+1]:=false;
		        writeln((x1+x2)div 2+1,' ',(y1+y2)div 2,' ',2)
              end;
            3:begin
		        g[(x1+x2)div 2,(y1+y2)div 2+1]:=false;
		        g[(x1+x2)div 2,(y1+y2)div 2]:=false;
		        g[(x1+x2)div 2+1,(y1+y2)div 2+1]:=false;
		        writeln((x1+x2)div 2,' ',(y1+y2)div 2+1,' ',3)
              end;
            4:begin
		        g[(x1+x2)div 2,(y1+y2)div 2]:=false;
		        g[(x1+x2)div 2,(y1+y2)div 2+1]:=false;
		        g[(x1+x2)div 2+1,(x1+x2)div 2]:=false;
		        writeln((x1+x2)div 2,' ',(y1+y2)div 2,' ',4)
              end
      end;
      work(x1,y1,(x1+x2)div 2,(y1+y2)div 2);      {对左上角分治}
      work(x1,(y1+y2)div 2+1,(x1+x2)div 2,y2);    {对右上角分治}
      work((x1+x2)div 2+1,y1,x2,(y1+y2)div 2);    {对左下角分治}
      work((x1+x2)div 2+1,(y1+y2)div 2+1,x2,y2)   {对右下角分治}
    end
end;

Begin {main}
  init;
  work(1,1,n,n);{对（1,1）到（n,n）范围内求解}
  close(input);
  close(output)
end.