残缺的棋盘

粉色区域为破损区域，先将棋盘看做四大区域，在棋盘的中心点附近添加色块，要求是四大区域中有破损的那一块不添加色块，得到黄色区域，然后将四大区域的每块都看做是一张棋盘进行递归

（这时我老师当初讲的）

当k>0时，将2^k×2^k棋盘分割为4个2^k-1×2^k-1 
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个硬纸板覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1

残缺的棋盘

发布时间: 2017年5月23日 11:21   时间限制: 1000ms   内存限制: 128M

描述

有一正方形棋盘，其边长为2^k（1<k<10），如图a所示，其中有一格损坏。现在想用图b所示形状的硬纸板将没有坏的所有格子盖起来。而硬纸板不得放入坏格中和棋盘外。编程输出一种覆盖方案

输入

输入: k  残缺格的坐标x,y（0<=x,y<2^k）

输出

输出: 数字方阵,用7表示残缺的格

样例输入1 复制

2 1 3

样例输出1

1 1 2 2 
1 2 2 2 
1 1 2 4 
1 7 4 4 

#include<stdio.h>
int an[1100][1100];
void chess(int size,int x,int y,int posx,int posy);
int main()
{
	int k,x,y;
	scanf("%d%d%d",&k,&x,&y);
	chess((1<<k),y,x,0,0);
	an[y][x]=7;
	for(int i=0;i<(1<<k);i++)
	{
		for(int j=0;j<(1<<k);j++)
		{
			printf("%d ",an[i][j]);
		}
		if(1!=(1<<k)-1)
			putchar('\n');
	}
	return 0;
}
void chess(int size,int x,int y,int posx,int posy)
{
	if(size==1)
		return ;
	int s=(size>>1);
	if(x<posx+s&&y<posy+s)
	{
		an[posx+s-1][posy+s]=4;
		an[posx+s][posy+s-1]=4;
		an[posx+s][posy+s]=4;
		chess(s,x,y,posx,posy);
		chess(s,posx+s-1,posy+s,posx,posy+s);
		chess(s,posx+s,posy+s-1,posx+s,posy);
		chess(s,posx+s,posy+s,posx+s,posy+s);
	}
	else if(x<posx+s&&y>=posy+s)
	{
		an[posx+s-1][posy+s-1]=3;
		an[posx+s][posy+s-1]=3;
		an[posx+s][posy+s]=3;		
		chess(s,posx+s-1,posy+s-1,posx,posy);
		chess(s,x,y,posx,posy+s);
		chess(s,posx+s,posy+s-1,posx+s,posy);
		chess(s,posx+s,posy+s,posx+s,posy+s);
	}
	else if(x>=posx+s&&y<posy+s)
	{
		an[posx+s-1][posy+s-1]=2;
		an[posx+s-1][posy+s]=2;
		an[posx+s][posy+s]=2;		
		chess(s,posx+s-1,posy+s-1,posx,posy);
		chess(s,posx+s-1,posy+s,posx,posy+s);
		chess(s,x,y,posx+s,posy);
		chess(s,posx+s,posy+s,posx+s,posy+s);
	}
	else if(x>=posx+s&&y>=posy+s)
	{
		an[posx+s-1][posy+s-1]=1;
		an[posx+s-1][posy+s]=1;
		an[posx+s][posy+s-1]=1;	
		chess(s,posx+s-1,posy+s-1,posx,posy);
		chess(s,posx+s-1,posy+s,posx,posy+s);
		chess(s,posx+s,posy+s-1,posx+s,posy);
		chess(s,x,y,posx+s,posy+s);
	}
}