|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 p62273470 于 2011-12-4 20:59 编辑
什么是棋盘覆盖问题?
答:在一个(2^k) × (2^k) 个 方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中出现的位置有4^k情形,因而有4^k种不同的棋盘。图a所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图b所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊棋盘方格以外的所有方格,且任何两个L型骨牌不得重叠覆盖。
分析方法:
分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格(这句话很重要),从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘,由于棋盘只有一个特殊棋盘,所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘,以便采用递归的方法求解,可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处(要理解这句话),如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略,直至将棋盘分割为1*1的子棋盘。
数据结构设计:
(1)棋盘:可以一个二维数组board[size][size]表示一个棋盘,其中,size = 2^k。为了在递归处理的过程中使用同一个棋盘,将数组board设置为全局变量。
(2)子棋盘:子棋盘由原始棋盘数组board的行下标tr,列下标tc表示。
(3)特殊方格:用board[dr][dc]表示特殊方格,dr和dc表示该特殊方格的在二维数组board中的下标
(4)L型骨牌:一个(2^k)*(2^k)的棋盘中有一个特殊方格,所以用到L型骨牌的个数为(4^k - 1)/3,将所有L型骨牌从1开始连续编号,同一个骨牌有3个方格组成,这3个方格用同一个编号。
代码如下:
- // 棋盘覆盖
- #include<iostream.h>
- #include <iomanip.h>
- int Board[8][8]={0};//定义棋盘并初始化棋盘
- void ChessBoard(int tr,int tc,int dr,int dc,int size,int &tile);
- void main()
- {
- int tile=0;
- cout<<"请输入特殊盘的下标号:"<<endl;
- int x,y;
- cin>>x>>y;
- ChessBoard(0,0,x,y,8,tile);
- cout<<endl<<endl;
- for(int i=0;i<8;i++)
- {
- for(int j=0;j<8;j++)
- {
- cout<<setw(2)<<Board[i][j]<<" ";
- }
- cout<<endl;
- }
- }
- void ChessBoard(int tr,int tc,int dr,int dc,int size,int &tile)
- {//采用分治策略的棋盘算法 c是列,r是行
- if(size==1)
- return;
- ++tile;//L型骨牌号
- int s=size/2;//分割棋盘
- if(dr<tr+s&&dc<tc+s)
- {//特殊方格在左上角棋盘中
- Board[tr+s-1][tc+s]=tile;//覆盖右上角子棋盘的左下角
- Board[tr+s][tc+s-1]=tile;//覆盖左下角子棋盘的右上角
- Board[tr+s][tc+s]=tile;//覆盖右下角子棋盘 的左上角
- ChessBoard(tr,tc,dr,dc,s,tile);//覆盖左上角子棋盘
- ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
- ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
- ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
- }
- else if(dr<tr+s&&dc>=tc+s)
- {//特殊方格在右上角棋盘中
- Board[tr+s-1][tc+s-1]=tile;
- Board[tr+s][tc+s-1]=tile;
- Board[tr+s][tc+s]=tile;
- ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
- ChessBoard(tr,tc+s,dr,dc,s,tile);//覆盖右上角子棋盘
- ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
- ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
- }
- else if(dr>=tr+s&&dc<tc+s)
- {//特殊方格在左下角棋盘中
- Board[tr+s-1][tc+s-1]=tile;
- Board[tr+s-1][tc+s]=tile;
- Board[tr+s][tc+s]=tile;
- ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
- ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
- ChessBoard(tr+s,tc,dr,dc,s,tile);//覆盖左下角子棋盘
- ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
- }
- else if(dr>=tr+s&&dc>=tc+s)
- {//特殊方格在右下角棋盘中
- Board[tr+s-1][tc+s-1]=tile;
- Board[tr+s-1][tc+s]=tile;
- Board[tr+s][tc+s-1]=tile;
- ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
- ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
- ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
- ChessBoard(tr+s,tc+s,dr,dc,s,tile);//覆盖右下角子棋盘
- }
- else
- cout<<"你妹,错了!"<<endl;
- }
复制代码
递归函数:递归函数工作原理介绍
|
|