棋盘覆盖算法.doc

棋盘覆盖算法.doc

ID:56709661

大小:38.00 KB

页数:8页

时间:2020-07-05

棋盘覆盖算法.doc_第1页
棋盘覆盖算法.doc_第2页
棋盘覆盖算法.doc_第3页
棋盘覆盖算法.doc_第4页
棋盘覆盖算法.doc_第5页
资源描述:

《棋盘覆盖算法.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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

2、盘转化为棋盘。二、程序(1)新建一个基于对话框的工程Ex0420Chess。(2)打开类视图,为CEx0420ChessDlg类添加以下成员变量和函数:inttile;//当前方块int**board;//指向棋盘的指针intm_dw;//棋盘每一格的宽度voidchessBoard(inttr,inttc,intdr,intdc,intsize);//棋盘覆盖算法voidDrawSubBoard(intx,inty,intw,intc);//画棋盘的x行,y列的方块,w表示宽度,c表示颜色值(3)在对话框上增加三个编辑框,ID分别

3、IDC_K、IDC_DR和IDC_DC,并为他们分别关联一个int型的变量m_k、m_dr和m_dc。然后添加三个按钮,ID分别为IDC_DRAW、IDC_DRAWBOAR和DIDC_CLEAR,标题分别为画棋盘、覆盖和清空。(4)本实验棋盘的大小固定为,k值越大,方格越多,这时每个方格的尺寸越小。为给每个L型骨牌填充不同的颜色,程序中将title的值转换成颜色值,画一个方格的函数DrawSubBoard()的定义如下:voidCEx0420ChessDlg::DrawSubBoard(intx,inty,intw,intc){CC

4、lientDCdc(this);COLORREFclr;clr=RGB(c*c/256,c*c*c/256,c*c*c*c/256);//将c值转换成颜色值CBrushbr(clr);CRectr;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()函数源程序如下:voidCEx0420Ch

5、essDlg::chessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;Sleep(500);intt=this->tile++;//L型骨牌号ints=size/2;//分割棋盘//覆盖左上角子棋盘if(dr

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

7、);this->DrawSubBoard(tr+s-1,tc+s,m_dw,t);}//覆盖左下角子棋盘if(dr>=tr+s&&dcDrawSubBoard(tr+s,tc+s-1,m_dw,t);}//覆盖右下角子棋盘if(dr>=tr+s&&dc>=tc+s)//

8、特殊方格在此棋盘中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,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。