《棋盘覆盖问题(Tromino谜题)》由会员分享，可在线阅读，更多相关《棋盘覆盖问题(Tromino谜题)（20页珍藏版）》请在金锄头文库上搜索。
1、棋盘覆盖问题在一个2CX2k(Re0)个方格组成的棋盘中,雾幕一个方格与其他方格不同，称该方格为特殊棋盘覆盖问题要求用如图Cb)所示的L型骨牌覆盖给定棋提上除特殊方格以外的所有方格,且骨牌之间不得有重叙。(b)4种不同形状的L型骨牌(a)c2时的一种棣盘ec一心suusiisml分治策略*技巧在于划分棋盘,使每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋指覆盖问题2MX2el|20X2e。振2M1X2e1|2mX2el(a)棋盘分割曹b看构造相同子问题sssuussiuuuseiiii垣下面介绍棋盘覆盖问题中数据结构的设计:(1)棋盘:用二维数组boardsizesize表示一个
2、棋盘,其中,size=2K。为了在递归处理的过程中使用同一个棋盘,将数组board设为全局变量;(2)子棋盘:在棋盘数组boardsizesize中,由子棋盘左上角的下标tr、tc和棋盘边长s表示;(3)特殊方格:用boarddrdc表示,drhdc是该特殊方格在棋盘数组boardq(4)L型骨牌:一个2X24时P的下标;棋盘中有一个特殊方格,所以,用到L型骨牌的个数为(4K-1)/3,将所有L型骨牌从1开始连续编号,个全局变量t表_一棋盘覆盖问题中的数据结构圆算法一一桥监穆萱一11MvoidChessBoardfinttr,intte,intdrintdcintsize)trfntc是棋盘左
3、上角的下标,drfdc是特殊方格的下标,1size是槲盘的大小,t已初始化为01)认(size=刀return;/桓揣只有一个方格旦是特殊方格t+;川L埚骨牌号s=size/2;川划分桥盘1覆盖左上角子模盟if(drtf+$&dtc+川特殊方格在左上角孔栗盘中ChessBoardttr,tc,ddc,sj;/途归处理子桥盘elsef丿用t号L型骨牌覆盎右下角,再递归处理子棋盘boardtr+s-tc+s一1=一ChessBoardttr,tc,trys-1,tc+s-1,s);/瞥盖右上角子棣盘:if(dr=tc+s)八特殊方格在右上角子棣盘中“ChessBoardttrtc+s,drdcs);/逊归处理子棋盘:else人用t号L型骨牌覆盖左下角,再递归处理子棣盘boardtr+s-人tc+引=一ChessBoardttrtc+s,trys-1,tc+s,s);】八覆盖左下角子棋盘if(dr=tr+s&dc=tf+s&dc=tc+s八特殊方格在右下角子模盘中,ChessBoardttr+s,tc+s,dr,dc,sj;/逵归处理子棣盘else人用t号L型骨牌覆盘左上角,再递归处理子模盘boardtr+stc+=一ChessBoardttr+s,tc+s,trys,tc+s,s);
