c语言实现棋盘覆盖问题.doc

c语言实现棋盘覆盖问题.doc棋盘覆盖问题
问题描述：在一个2kX 2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格 为一特殊方格， 且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中， 要用图示的 4 种不同形态的 L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2个L型骨牌不得重叠
覆盖。
代码： #include<>
int tile=O;〃整型变量，记录 L型骨牌的数量
int Matrix[100][100];// 定义数据结构
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{〃tr和tc分别是棋盘左上角方格的行号、列号； dr和de分别是特殊方格的行号、列号 if(size==1) return;
int t=tile++;//L 型骨牌号，初值为 0
int s=size/2;〃 分割棋盘
if(drvtr+s&&dcvtc+s)〃用L型骨牌号覆盖左上角子棋盘
ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盘中
else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右下角
Matrix[tr+s-1][tc+s-1]=t; // 覆盖本子棋盘中的其余方格 ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
}
if(dr<tr+s&&dc>=tc+s)〃用L型骨牌号覆盖右上角子棋盘
ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盘中
else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左下角
Matrix[tr+s-1][tc+s]=t;// 覆盖本子棋盘中的其余方格 ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s&&dcvtc+s)//用L型骨牌号覆盖左下角子棋盘 ChessBoard(tr+s,tc,dr,dc,s);// 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右上角
Matrix[tr+s][tc+s-1]=t;// 覆盖本子棋盘中的其余方格 ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
}
if(dr>=tr+s&&dc>=tc+s)〃用L型骨牌号覆盖右上角子棋盘 ChessBoard(tr+s,tc+s,dr,dc,s);〃 特殊方格在此棋盘中 else
{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左上角
Matrix[tr+s][tc+s]=t;// 覆盖本子棋盘中的其余方格 ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}
int main() {
int size,r,c,row,col;
〃memset(Matrix,0,sizeof(Matrix));
for(int i=0;iv=100;i++)〃 初始化 为零
{
for(int j=0;jv=100;j++)
{ Matrix[i][j]=0;
}
}
scanf("%d", &size