jzoj 1418. 【2012.04.14普及组】棋盘覆盖

发布于 2019-03-24  984 次阅读


题目描述

在一个2^k× 2^k个方格组成的棋盘中恰有一个方格与其他方格不同(图中标记为-1 的方格),称之为特殊方格。现用L 型(占3 个小格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到的纸片数恰好是(4^k−1) / 3 。在下表给出的一个覆盖方案中,k=2,相同的3个数字构成一个纸片。
这里写图片描述

输入

输入文件Chessboard.in,共两行,第一行一个数N为棋盘的大小,N满足条件N=2^K,1<=K<=10.
第二行,两个数x,y,表示棋盘中那一个与其它方格不同的位置,x表示行,y表示列.

输出

输出文件Chessboard.out,输出N行N列,共N×N个数,表示用L 型(占3 个小格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠的方法.其中的数表示L型纸片覆盖的顺序编号, 不同的L型纸片用不同的编号,同一个L型纸片占据的三个位置相同,编号从1开始,特殊方格用-1标志;每两个数之间用一个空格隔开,每行最末一个数后面没有空格.

思路

这是一道分治的题目,首先从中点先4个方向进行4分,然后把有空格的第方用L型纸片在最中间相应的地方补上就可以了

var
  n,x,y,s,i,j:integer;
  a:array[1..100,1..100] of integer;
procedure f(l,r,x,y,o:integer);
begin
  if o=1 then exit
    else inc(s);
  o:=o div 2;
  if x>=l+o then
    begin
      if y>=r+o then
        begin
          a[l+o-1,r+o-1]:=s;
          a[l+o-1,r+o]:=s;
          a[l+o,r+o-1]:=s;
          f(l,r,l+o-1,r+o-1,o);
          f(l+o,r,l+o,r+o-1,o);
          f(l,r+o,l+o-1,r+o,o);
          f(l+o,r+o,x,y,o);
        end
      else
        begin
          a[l+o-1,r+o-1]:=s;
          a[l+o-1,r+o]:=s;
          a[l+o,r+o]:=s;
          f(l,r,l+o-1,r+o-1,o);
          f(l+o,r,x,y,o);
          f(l,r+o,l+o-1,r+o,o);
          f(l+o,r+o,l+o,r+o,o);
        end
    end
  else
    begin
      if y>=r+o
        then
          begin
            a[l+o-1,r+o-1]:=s;
            a[l+o,r+o-1]:=s;
            a[l+o,r+o]:=s;
            f(l,r,l+o-1,r+o-1,o);
            f(l+o,r,l+o,r+o-1,o);
            f(l,r+o,x,y,o);
            f(l+o,r+o,l+o,r+o,o);
          end
        else
          begin
            a[l+o-1,r+o]:=s;
            a[l+o,r+o-1]:=s;
            a[l+o,r+o]:=s;
            f(l,r,x,y,o);
            f(l+o,r,l+o,r+o-1,o);
            f(l,r+o,l+o-1,r+o,o);
            f(l+o,r+o,l+o,r+o,o);
          end
    end;
end;

begin
  readln(n);
  readln(x,y);
  f(1,1,x,y,n);
  for i:=1 to n do
    begin
      for j:=1 to n do
        write(a[i,j]:5);
      writeln;
    end;
end.
]]>