棋盘覆盖算法

1、用Visual C+6.0实现棋盘覆盖分治算法1、 问题描述在一个个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘唯一特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。当时，将棋盘分割为4个子棋盘，特殊方格必位于4个较小子棋盘之一中，将其余3个子棋盘中无特殊方格。为了将这3个无特殊方格子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖着3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘转化为棋盘。2、 程序（1）新建一个基于对话框的工程Ex0

2、420Chess。（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

3、和m_dc。然后添加三个按钮，ID分别为IDC_DRAW、IDC_DRAWBOAR和DIDC_CLEAR，标题分别为画棋盘、覆盖和清空。（4）本实验棋盘的大小固定为，k值越大，方格越多，这时每个方格的尺寸越小。为给每个L型骨牌填充不同的颜色，程序中将title的值转换成颜色值，画一个方格的函数DrawSubBoard（）的定义如下：void CEx0420ChessDlg:DrawSubBoard(int x ,int y ,int w, int c)CClientDC dc(this);COLORREF clr;clr= RGB(c*c/256,c*c*c/256,c*c*c*c/256);

4、/将c值转换成颜色值CBrush br(clr);CRect r;r.top=10+x*m_dw;r.bottom=r.top+m_dw;r.left=10+y*m_dw;r.right=r.left+m_dw;dc.FillRect(&r,&br);使用分治算法覆盖棋盘，为清楚看到覆盖棋盘的顺序，每次覆盖完一个L型骨牌后停顿0.5秒，chessBoard()函数源程序如下：void CEx0420ChessDlg:chessBoard(int tr, int tc, int dr, int dc, int size)if (size = 1) return;Sleep(500

5、);int t = this->tile+; / L型骨牌号 int s = size/2; / 分割棋盘 / 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s);else/ 此棋盘中无特殊方格 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t;/ 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);this->DrawSubBoard(tr+s-1, tc+s-1,

6、m_dw,t);/递归过程中，此子棋盘中没有特殊方格，调用DrawSubBoard()函数画一个方格，并填充颜色 / 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else/ 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);this->DrawSubBoard(tr+s-1, tc+

7、s,m_dw,t); / 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else / 用 t 号L型骨牌覆盖右上角 boardtr + stc + 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 &

8、gt;= tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + 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)this

9、->MessageBox("为了方便演示，建议输入1-5的整数")；elsethis->OnClear();CClientDC dc(this);/当输入一个新的k值时，清空原有图形int k=this->m_k; this->m_dw=256/(int)pow(2,k);/棋盘区域大小固定为256*256，根据k值计算方格宽度for(int i=10;i<267;i+=m_dw)/画棋盘dc.MoveTo(10,i);dc.LineTo(267,i);dc.MoveTo(i,10;dc.LineTo(i,267);/点击“覆盖”按钮消息响应函

10、数Void CEx0420ChessDlg:Ondrawboard()UpdateData();if(m_dr>=(int)pow(2,m_k)|m_dc>=(int)pow(2,m_k)|m_dr<0|m_dc<0)/判断dr，dc中数据是否溢出this->MessageBox("特殊方格行号或列号错误，请重新输入！")；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);r.top = 10+m_dr*w;r.bottom = r.top+w;r.left = 10+m_dc*w;r.right = r.left+w;dc.FillRect(&r,&br);Sleep(1000);this->chessBoard(0,0,this->m_dr,this->m_dc,(int)pow(2,this->m_k);点击“清空”按钮清空棋盘区域原有图形void CEx04