《算法设计与分析》棋盘覆盖问题


《算法设计与分析》上机:2.6 棋盘覆盖问题

//《算法设计与分析》上机:2.6 棋盘覆盖问题

#include <stdio.h>

#define N 16          //此处定义方格大小
int board[N][N]={0};  //表示棋盘
int tile=0;           //全局变量。表示L型骨牌的编号,初始值=0

void chessBoard(int tr,int tc,int dr,int dc,int size)
{
	if(size==1) return;
	int t;
	t=tile++;
	int s;
	s=size/2;
	//覆盖左上角
	if(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 display()
{
	int i,j;
	printf("n棋盘覆盖:n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf("%2d ",board[i][j]);
		printf("n");
	}
}
int main()
{
	int tr=0,tc=0;//tr,tc分别表示左上角方格的行号和列号
	int dr,dc;
	printf("请输入特殊方格所在的行号dr和列号dc:n");
	printf("dr=");
	scanf("%d",&dr);
	printf("dc=");
	scanf("%d",&dc);
	chessBoard(tr,tc,dr,dc,N);
	display();
	return 0;
}

发表评论