ch_b.cpp

本程序可以动态显示棋盘覆盖的过程

#include "iostream.h"
#include "stdlib.h"
#include "time.h"
#define M 32//假定棋盘的规格为32*32

int board[M][M]={0};//board表示棋盘
int tile=1;//tile表示L型骨牌的编号
//函数chessboard(int tr,int tc,int dr,int dc,int size)用于实现残缺棋盘问题
//其中，tr表示棋盘左上角方格的行号；tc表示棋盘左上角方格的列号；
//dr表示特殊方格所在的行号；dc表示特殊方格所在的列号；size表示2^k,棋盘规格为2^k*2^k
void chessboard(int tr,int tc,int dr,int dc,int size)
{
	if(size==1) return;
	int t=tile++,//L型骨牌号
		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;//用t号L型骨牌覆盖右下角
		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;//用t号L型骨牌覆盖左下角
		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;//用t号L型骨牌覆盖左下角
		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;//用t号L型骨牌覆盖左下角
		chessboard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其它方格
	}
}

void main()
{
	int k,n=1,j;
	cout<<"棋盘矩阵的规格为2^k*2^k,请输入相应的k值:";
	while(1)//判断k的合法性，本程序假定k值不大于4
	{
		cin>>k;
		if(k<=4&&k>0) break;
		cout<<"k值超过预定范围，请重新输入!\n\n";
        cout<<"棋盘矩阵的规格为2^k*2^k,请输入相应的k值:";
	}
	for(int i=0;i<k;i++) n*=2;
	cout<<"棋盘矩阵规格为"<<n<<"*"<<n<<endl;
	cout<<"特殊方格的位置坐标随机给出，此时";
	//给出随机数
	srand((unsigned)time(NULL));
	j=rand()%n;
	i=rand()%n;
	cout<<"特殊方格(在棋盘中以0表示)的位置坐标为("<<j<<","<<i<<")\n";
	cout<<"要覆盖该棋盘，共需"<<(n*n-1)/3<<"块L型骨牌\n";
	cout<<"覆盖情况如下(用同一数字代表一块骨牌)：\n";
	chessboard(0,0,j,i,n);
	for(i=0;i<n;i++)
	{
		for(k=0;k<n;k++)
		{
			cout<<board[i][k]<<" ";
			if(board[i][k]<10) cout<<" ";
		}
		cout<<endl;
	}
}