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


《算法设计与分析》上机:2.6 棋盘覆盖问题
[c]
//《算法设计与分析》上机: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;
}
[/c]

发表评论