棋盘覆盖问题（用分治法求解）

p62273470

什么是棋盘覆盖问题？
答：在一个(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个方格用同一个编号。


代码如下：

1. // 棋盘覆盖
   
2. #include<iostream.h>
   
3. #include <iomanip.h>
   
4. 
   
5. int Board[8][8]={0};//定义棋盘并初始化棋盘
   
6. void ChessBoard(int tr,int tc,int dr,int dc,int size,int &tile);
   
7. 
   
8. void main()
   
9. {
   
10. int tile=0;
    
11. cout<<"请输入特殊盘的下标号:"<<endl;
    
12. int x,y;
    
13. cin>>x>>y;
    
14. ChessBoard(0,0,x,y,8,tile);
    
15. cout<<endl<<endl;
    
16. for(int i=0;i<8;i++)
    
17. {
    
18.     for(int j=0;j<8;j++)
    
19.     {
    
20.         cout<<setw(2)<<Board[i][j]<<" ";
    
21.     }
    
22.     cout<<endl;
    
23. }
    
24. 
    
25. }
    
26. 
    
27. void ChessBoard(int tr,int tc,int dr,int dc,int size,int &tile)
    
28. {//采用分治策略的棋盘算法 c是列，r是行
    
29. if(size==1)
    
30. return;
    
31. 
    
32. ++tile;//L型骨牌号
    
33. int s=size/2;//分割棋盘
    
34. 
    
35. if(dr<tr+s&&dc<tc+s)
    
36. {//特殊方格在左上角棋盘中
    
37. Board[tr+s-1][tc+s]=tile;//覆盖右上角子棋盘的左下角
    
38. Board[tr+s][tc+s-1]=tile;//覆盖左下角子棋盘的右上角
    
39. Board[tr+s][tc+s]=tile;//覆盖右下角子棋盘 的左上角
    
40. 
    
41. ChessBoard(tr,tc,dr,dc,s,tile);//覆盖左上角子棋盘
    
42. ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
    
43. ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
    
44. ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
    
45. }
    
46. else if(dr<tr+s&&dc>=tc+s)
    
47. {//特殊方格在右上角棋盘中
    
48. Board[tr+s-1][tc+s-1]=tile;
    
49. Board[tr+s][tc+s-1]=tile;
    
50. Board[tr+s][tc+s]=tile;
    
51. 
    
52. ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
    
53. ChessBoard(tr,tc+s,dr,dc,s,tile);//覆盖右上角子棋盘
    
54. ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
    
55. ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
    
56. }
    
57. else if(dr>=tr+s&&dc<tc+s)
    
58. {//特殊方格在左下角棋盘中
    
59. Board[tr+s-1][tc+s-1]=tile;
    
60. Board[tr+s-1][tc+s]=tile;
    
61. Board[tr+s][tc+s]=tile;
    
62. 
    
63. ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
    
64. ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
    
65. ChessBoard(tr+s,tc,dr,dc,s,tile);//覆盖左下角子棋盘
    
66. ChessBoard(tr+s,tc+s,tr+s,tc+s,s,tile);//覆盖右下角子棋盘
    
67. }
    
68. else if(dr>=tr+s&&dc>=tc+s)
    
69. {//特殊方格在右下角棋盘中
    
70. Board[tr+s-1][tc+s-1]=tile;
    
71. Board[tr+s-1][tc+s]=tile;
    
72. Board[tr+s][tc+s-1]=tile;
    
73. 
    
74. 
    
75. ChessBoard(tr,tc,tr+s-1,tc+s-1,s,tile);//覆盖左上角子棋盘
    
76. ChessBoard(tr,tc+s,tr+s-1,tc+s,s,tile);//覆盖右上角子棋盘
    
77. ChessBoard(tr+s,tc,tr+s,tc+s-1,s,tile);//覆盖左下角子棋盘
    
78. ChessBoard(tr+s,tc+s,dr,dc,s,tile);//覆盖右下角子棋盘
    
79. }
    
80. else
    
81. cout<<"你妹，错了!"<<endl;
    
82. 
    
83. 
    
84. }
    
85. 
    

复制代码

递归函数：递归函数工作原理介绍

驻留的习惯

好强大！！！！！！！！！！

vanentu

好强大！！！

EntU

好强大

溯月0503

{:1_1:}

vank

强烈建议大家看看

waliemiao

强烈建议大家看看