硬生生将C++改成了C

$分治$

1.题目大意

简单来说就是有一个$2^k \times 2^k$ 的方阵，除了一个方格外，都要用 $L$形的骨牌覆盖，且不能重叠。

2.解题思路

现 $L$ 型（占 $3$ 个小方格）骨牌覆盖棋盘上除特殊方格外的所有部分，各骨牌不得重叠，于是，用到的骨牌数恰好是$\displaystyle \frac{(4^k−1)}{3}$ 个。在下表给出的覆盖方案中，$k=2$，相同的3个数字构成一个骨牌。我的程序使用​分治法​，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。如果我们所在小棋盘有特殊方格，那我们“转移阵地”，到没有特殊方格的地方放置骨牌，然后继续分治，直到棋盘边长为$1$，就回溯。

#include<stdio.h>
int board[3200][3200], tile; /* tile为纸片编号 */
void chessboard( int tr, int tc, int dr, int dc, int size )
/* dr,dc依次为特殊方格的行、列号 */
{
	int t, s;
	if ( size == 1 )
		return ;
		t = tile++;
	s = size / 2;
	if ((dr<tr+s)&&(dc<tc+s) / dr<tr+s&&dc<tc+s )
		chessboard( tr, tc, dr, dc, s );
	else{
		board[tr + s -1][tc + s -1] = t;
		chessboard(tr,tc,tr+s-1,tc+s-1,s);
	}
	if ( dr < tr + s && dc >= tc + s )
		chessboard( tr, tc + s, dr, dc, s );
	else{
		board[tr + s -1][tc + s] = t;
		chessboard(tr,tc+s,tr+s-1,tc+s,s);
	}
	if ( dr >= tr + s && dc < tc + s )
		chessboard( tr + s, tc, dr, dc, s );
	else{
		board[tr + s][tc + s -1] = t;
		chessboard(tr+s,tc,tr+s,tc+s-1,s);
	}
	if ( dr >= tr + s && dc >= tc + s )
		chessboard( tr + s, tc + s, dr, dc, s );
	else{ board[tr + s][tc + s] = t;
	      chessboard(tr+s,tc+s,tr+s,tc+s,s); }
}

void prtl(int n )
{
	int i, j;
	for ( i =1; i <= n; i++ )
	{
		for ( j =1; j <= n; j++ )
			if(board[i][j]!=-1)printf("%d ",board[i][j]);//std::cout<<board[i][j]<<' ';//printf("%d ",&board[i][j]);
			else printf("0 ");
		printf("\n");
	}
}


int main()
{
	int size, dr, dc;
//	cout << "input size(4/8/16/64):" << endl;
	scanf("%d",&size);
//	cout << "input the position of special block(x,y):" << endl;
	scanf("%d%d",&dr,&dc);
	board[dr][dc] = -1;
	tile++;
	chessboard( 1, 1, dr, dc, size );
	prtl(size );
	return 0;
}