怎样保持身心健康-吹泡泡游戏

学习资料

用Visual C++6.0实现棋盘覆盖分治算法
一、问题描述

kk
2?2个方格 组成的棋盘中，恰有一个方格与其他方格在一个不同，称
该方格为一特殊方格，且称该棋盘唯一特殊棋盘 。在棋盘覆盖问题中，
要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外
的所 有方格，且任何2个L型骨牌不得重叠覆盖。

k?0
kkk-1k-1
2 22?2?子棋盘，特殊个时，将当棋盘分割为4方格必位于4个
较小子棋盘之一中，将其余3个子棋盘 中无特殊方格。为了将这3个
无特殊方格子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖着3
个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖
问题。递归的使用这种分割，直至棋
1?1
。 盘转化为棋盘
二、程序
（1）新建一个基于对话框的工程Ex0420Chess。
（2）打开类视图，为CEx0420ChessDlg类添加以下成员变量和函数：
int tile;
当前方块
指向棋盘的指针 int **board;
int m_dw; 棋盘每一格的宽度
void chessBoard(int tr, int tc, int dr, int dc, int size); 棋盘覆盖算法

仅供学习与参考．
学习资料

void DrawSubBoard(int x, int y, int w, int c); 画棋盘的x行，y列的方

块，w表示宽度，c表示颜色值 （3）在对话框上增加三个编辑框，ID分别IDC_K、IDC_DR和
IDC_DC，并为他们 分别关联一个int型的变量m_k、m_dr和m_dc。
然后添加三个按钮，ID分别为IDC_D RAW、IDC_DRAWBOAR和
DIDC_CLEAR，标题分别为画棋盘、覆盖和清空。 < br>256?256，k（4）本实验棋盘的大小固定为值越大，方格越多，这时
每个方格的尺寸越小 。为给每个L型骨牌填充不同的颜色，程序中将
title的值转换成颜色值，画一个方格的函数Dra wSubBoard（）的定
义如下：
void CEx0420ChessDlg::DrawSubBoard(int x ,int y ,int w, int c)
{
CClientDC dc(this);
COLORREF clr;
clr= RGB(c*c256,c*c*c256,c*c*c*c256); 值转换成c将 颜色值
CBrush br(clr);
CRect r;
=10+x*m_dw;
=+m_dw;
=10+y*m_dw;

仅供学习与参考．
学习资料

=+m_dw;
ct(&r,&br);

}
使用分治算 法覆盖棋盘，为清楚看到覆盖棋盘的顺序，每次覆盖完一
个L型骨牌后停顿0.5秒，chessBoa rd()函数源程序如下：

void CEx0420ChessDlg::chessBoard(int tr, int tc, int dr, int dc, int size)
{
if (size == 1) return;
Sleep(500);
int t = this->tile++; L型骨牌号
int s = size2; 分割棋盘
覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s) 特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
else
{ 此棋盘中无特殊方格 用 t 号L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
覆盖其余方格
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
this->DrawSubBoard(tr+s-1, tc+s-1,m_dw,t); 递归过程中，此子棋盘中没有特殊方格，调用DrawSubBoard()函数
画一个方格，并填 充颜色

仅供学习与参考．
学习资料

}

覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
特殊方格在此棋盘中
chessBoard(tr, tc+s, dr, dc, s);
else 此棋盘中无特殊方格
型骨牌覆盖左下角 L { 用 t 号 board[tr + s - 1][tc + s]
= t;
覆盖其余方格
chessBoard(tr, tc+s, tr+s-1, tc+s, s);

this->DrawSubBoard(tr+s-1, tc+s,m_dw,t);
}

覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
else
t 号L 型骨牌覆盖右上角 { 用 board[tr + s][tc + s
- 1] = t;

覆盖其余方格
chessBoard(tr+s, tc, tr+s, tc+s-1, s);

仅供学习与参考．
学习资料

this->DrawSubBoard(tr+s, tc+s-1,m_dw,t);
}

覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else
{ 用 t 号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
覆盖其余方格
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
this->DrawSubBoard(tr+s, tc+s,m_dw,t);
}
}
（5）为三个按钮分别添加消息响应函数
点击“画棋盘”按钮消息响应函数
void CEx0420ChessDlg::OnDraw()
{

UpdateData(); 更新编辑框中的数据，重要if(m_k>5)
的整数为了方便演示，桴獩?敍獳条?硯尨建议输入1-5
仅供学习与参考．
学习资料

)；
else{
this->OnClear();
CClientDC dc(this); 当输入一个新的k值时，清空 原有图形 int
k=this->m_k;
为定小固大棋this->m_dw=256(int)pow(2,k);盘区域 k值计算方格宽
度256*256，根据 画棋盘for(int i=10;i<267;i+=m_dw) {
(10,i);
(267,i);
(i,10;
(i,267);
}
}
}
点击“覆盖”按钮消息响应函数oid
CEx0420ChessDlg::Ondrawboard() V{
UpdateData();
if(m_dr>=(int)pow(2,m_k)|| m_dc>=(int)pow(2,m_k)||m_dr<0||m_
仅供学
习与参考．
学习资料

dc<0)

判断dr，dc中数据是否溢出
桴獩?敍獳条?硯尨特殊方格行号或列号错误，请重新输入！)；
else{
调用以下两个函数重新进行覆盖
this->OnClear();
this->OnDraw();
得到特殊方格的行号和列号后，将它用黑色填充，以做标记
CClientDC dc(this);
COLORREF clr;
clr = RGB(0,0,0);
CBrush br(clr);
CRect r;
int w = 256(int)pow(2,m_k);
= 10+m_dr*w;
= +w;
= 10+m_dc*w;
= +w;
ct(&r,&br);
Sleep(1000);
this->chess Board(0,0,this->m_dr,this->m_dc,(int)pow(2,this->m _k));

仅供学习与参考．
学习资料

}

}
点击“清空”按钮清空棋盘区域原有图形
void CEx0420ChessDlg::Onclear()
{
CClientDC dc(this);
gle(10,10,267,267);
}
二，注意
本程序定义了一个指向指针的指针**board，在使用时必须 进行初始
化，初始化的方法为：
board = new int *[50];
for(int i=0;i<50;i++)
board[i]=new int[50];



仅供学习与参考．