棋盘覆盖问题（分治法）

问题

在一个2^k×2^k (k≥0)个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4^k种不同的棋盘，图4.10(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题(chess cover problem)要求用图4.10(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

想法

如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0时，可将2^k×2^k的棋盘划分为4个2^(k-1)×2^(k-1)的子棋盘，如图4.11(a)所示。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图4.11(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。

 1 //棋盘覆盖问题
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 using namespace std;
 6 int board[1025][1025];
 7 static int tile = 1;
 8 
 9 void ChessBoard(int tr,int tc,int dr,int dc,int size){
10     if( size == 1 )
11         return ;
12         
13     int t = tile++;
14     int s = size/2;
15     
16     if( dr<tr+s && dc<tc+s )
17         ChessBoard(tr,tc,dr,dc,s);
18     else{
19         board[tr+s-1][tc+s-1] = t;
20         ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
21     }
22     
23     if( dr<tr+s && dc>=tc+s )
24         ChessBoard(tr,tc+s,dr,dc,s);
25     else{
26         board[tr+s-1][tc+s] = t;
27         ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
28     }
29     
30     if( dr>=tr+s && tc<tc+s )
31         ChessBoard(tr+s,tc,dr,dc,s);
32     else{
33         board[tr+s][tc+s-1] = t;
34         ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
35     }
36     
37     if( dr>=tr+s && dc>=tc+s )
38         ChessBoard(tr+s,tc+s,dr,dc,s);
39     else{
40         board[tr+s][tc+s] = t;
41         ChessBoard(tr+s,tc+s,tr+s,tc+s,s); 
42     }
43     
44 }
45 
46 int main(){
47     int k;
48     while( scanf("%d",&k) != EOF ){
49         int size = 1<<k;
50         int x,y;
51         cin>>x>>y;//特殊方格的位置
52         ChessBoard(0,0,x,y,size);
53         for( int i = 0; i < size; i++ ){
54             for( int j = 0; j < size; j++ )
55                 printf("%d	",board[i][j]);
56             cout<<endl;
57         }
58         cout<<endl;             
59     }
60     return 0;
61 }