当前位置: 永利棋牌 > 小说 > 正文

棋盘覆盖递归分治,递归与分治之棋盘覆盖问题

时间:2019-10-01 13:19来源:小说
在一个2^k*2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。 棋盘覆盖问题(递归分治),棋盘覆盖递归分治        问题描

在一个2^k * 2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。

棋盘覆盖问题(递归分治),棋盘覆盖递归分治

   

   问题描述:

      在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘.
     下图–图(1)中的特殊棋盘是当k=3时16个特殊棋盘中的一个:

图片 1

图(1)

      题目要求在棋盘覆盖问题中,要用下图-图(2)所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.

图片 2

图(2)

题目包含多组测试数据,输入包含测试数据组数N,下面输入N组数据,每组数据,包括边长m和特殊方格的位置x,y。

input sample

2
2
0 0
8
2 2

output sample

CASE:1
0  1  
1  1  
CASE:2
3  3  4  4  8  8  9  9  
3  2  2  4  8  7  7  9  
5  2  0  6  10 10 7  11 
5  5  6  6  1  10 11 11 
13 13 14 1  1  18 19 19 
13 12 14 14 18 18 17 19 
15 12 12 16 20 17 17 21 
15 15 16 16 20 20 21 21

 

题解:当 k>0 时,将 2^k * 2^k 棋盘分割为 4 个 2^(k-1) * 2^(k-1) 子棋盘,如下图所示。

图片 3

特殊方格必位于 4 个较小子棋盘之一中,其余 3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,我们可以用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如下图所示,这 3 个子棋盘上被 L 型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题化为 4 个较小规模的棋盘覆盖问题。递归的使用 这种分割,直至棋盘简化为 1x1 棋盘。

图片 4

 

#include<iostream>
using namespace std;
int tile=1;                   //L型骨牌的编号(递增)
int b[100][100];  //棋盘
/*****************************************************
* 递归方式实现棋盘覆盖算法
* 输入参数:
* tr--当前棋盘左上角的行号
* tc--当前棋盘左上角的列号
* dr--当前特殊方格所在的行号
* dc--当前特殊方格所在的列号
* size:当前棋盘的:2^k
*****************************************************/
void chessBoard ( int tr, int tc, int dr, int dc, int size )
{
    if ( size==1 )    //棋盘方格大小为1,说明递归到最里层
        return;
    int t=tile++;     //每次递增1
    int s=size/2;    //棋盘中间的行、列号(相等的)
    //检查特殊方块是否在左上角子棋盘中
    if ( dr<tr+s && dc<tc+s )              //在
        chessBoard ( tr, tc, dr, dc, s );
    else         //不在,将该子棋盘右下角的方块视为特殊方块
    {
        b[tr+s-1][tc+s-1]=t;
        chessBoard ( tr, tc, tr+s-1, tc+s-1, s );
    }
    //检查特殊方块是否在右上角子棋盘中
    if ( dr<tr+s && dc>=tc+s )               //在
        chessBoard ( tr, tc+s, dr, dc, s );
    else          //不在,将该子棋盘左下角的方块视为特殊方块
    {
        b[tr+s-1][tc+s]=t;
        chessBoard ( tr, tc+s, tr+s-1, tc+s, s );
    }
    //检查特殊方块是否在左下角子棋盘中
    if ( dr>=tr+s && dc<tc+s )              //在
        chessBoard ( tr+s, tc, dr, dc, s );
    else            //不在,将该子棋盘右上角的方块视为特殊方块
    {
        b[tr+s][tc+s-1]=t;
        chessBoard ( tr+s, tc, tr+s, tc+s-1, s );
    }
    //检查特殊方块是否在右下角子棋盘中
    if ( dr>=tr+s && dc>=tc+s )                //在
        chessBoard ( tr+s, tc+s, dr, dc, s );
    else         //不在,将该子棋盘左上角的方块视为特殊方块
    {
        b[tr+s][tc+s]=t;
        chessBoard ( tr+s, tc+s, tr+s, tc+s, s );
    }
}

int main()
{
    int t,size,x,y,total=0;
    cin>>t;
    while(t--)
    {
        cin>>size;
        cin>>x>>y;
        total++;
        chessBoard (0,0,x,y,size );
         cout<<"CASE:"<<total<<endl;
        for ( int i=0; i<size; i++ )
        {
            for ( int j=0; j<size; j++ )
                cout<<b[i][j]<<" ";
            cout<<endl;
        }
    }
}

 

问题描述: 在一个2^k2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一...

 

显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘。

>_<: 问题描述:

下图所示的特殊棋盘为 k=2 时 16 个特殊棋盘中的一个。

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

                      

图片 5

      图片 6

>_<: **解决方法:**

 

当k>0时,将2^k X 2^k 棋盘分割为4个2^(k-1) X 2^(k-1)子棋盘,特殊格必位于四块小的棋盘之一中,其余3个子棋盘无特殊方格,为了将这3个无特殊的格子棋盘转化为特殊棋盘,我们可以用一个L型的骨牌覆盖这3个较小的企盼汇合处,从而将问题转化为4个较小规模的企盼覆盖问题,递归使用这种分割,直至棋盘划分为1的棋盘。

在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖。

图片 7

 

 1 #include<iostream>
 2 #include<iomanip>
 3 using namespace std;
 4 int tile=1;                   //L型骨牌的编号(递增)
 5 int board[100][100];//棋盘
 6 /*****************************************************
 7 * 递归方式实现棋盘覆盖算法
 8 * 输入参数:
 9 * tr--当前棋盘左上角的行号
10 * tc--当前棋盘左上角的列号
11 * dr--当前特殊方格所在的行号
12 * dc--当前特殊方格所在的列号
13 * size:当前棋盘的:2^k
14 *****************************************************/
15 void chessBoard(int tr,int tc,int dr,int dc,int size){
16     if(size==1)//棋盘方格大小为1,说明递归到最里层
17         return;
18     int t=tile++;//每次递增1
19     int s=size/2;//棋盘中间的行、列号(相等的)
20 
21     //检查特殊方块是否在左上角子棋盘中
22     if(dr<tr+s && dc<tc+s)//在
23         chessBoard(tr,tc,dr,dc,s);
24     else{//不在,将该子棋盘右下角的方块视为特殊方块
25         board[tr+s-1][tc+s-1]=t;
26         chessBoard(tr,tc,tr+s-1,tc+s-1,s);
27     }
28 
29     //检查特殊方块是否在右上角子棋盘中
30     if(dr<tr+s && dc>=tc+s)//在
31         chessBoard(tr,tc+s,dr,dc,s);
32     else{//不在,将该子棋盘左下角的方块视为特殊方块
33         board[tr+s-1][tc+s]=t;
34         chessBoard(tr,tc+s,tr+s-1,tc+s,s);
35     }
36 
37     //检查特殊方块是否在左下角子棋盘中
38     if(dr>=tr+s && dc<tc+s)//在
39         chessBoard(tr+s,tc,dr,dc,s);
40     else{//不在,将该子棋盘右上角的方块视为特殊方块
41         board[tr+s][tc+s-1]=t;
42         chessBoard(tr+s,tc,tr+s,tc+s-1,s);
43     }
44 
45     //检查特殊方块是否在右下角子棋盘中
46     if(dr>=tr+s && dc>=tc+s)//在
47         chessBoard(tr+s,tc+s,dr,dc,s);
48     else{//不在,将该子棋盘左上角的方块视为特殊方块
49         board[tr+s][tc+s]=t;
50         chessBoard(tr+s,tc+s,tr+s,tc+s,s);
51     }
52 }
53 
54 void main(){
55     while(true){
56         memset(board,0,sizeof(board));
57         tile=1;
58 
59         int size;
60 
61         cout<<"输入棋盘的size(大小必须是2的n次幂): ";
62         cin>>size;
63         int index_x,index_y;
64         cout<<"输入特殊方格位置的坐标: ";
65         cin>>index_x>>index_y;
66 
67         chessBoard (0,0,index_x,index_y,size);
68 
69         cout<<endl;
70         for(int i=0;i<size;i++){//输出棋盘覆盖
71             for(int j=0;j<size;j++ )
72                 cout<<setw(3)<<board[i][j]<<" ";
73             cout<<endl;
74         }
75         cout<<endl;
76     }
77 }

编辑:小说 本文来源:棋盘覆盖递归分治,递归与分治之棋盘覆盖问题

关键词: