题目描述
在一个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.
Comments NOTHING