0003算法笔记 - [分治法]分治法与二分搜索，棋盘覆盖问题(2)

棋盘覆盖程序如下：

[cpp] view plain copy

1. //2d6 棋盘覆盖问题 2. #include \

3. #include 4. using namespace std; 5.

6. int tile = 1;//全局变量 骨牌编号 7. int Board[4][4];//棋盘

8. void ChessBoard(int tr,int tc,int dr,int dc,int size); 9.

10. int main() 11. {

12. for(int i=0; i<4; i++) 13. {

14. for(int j=0; j<4; j++) 15. {

16. Board[i][j] = 0; 17. } 18. } 19.

20. ChessBoard(0,0,2,3,4); 21.

22. for(int i=0; i<4; i++) 23. {

24. for(int j=0; j<4; j++) 25. {

26. cout<

28. cout<

33. * tr : 棋盘左上角的行号，tc棋盘左上角的列号

34. * dr : 特殊方格左上角的行号，dc特殊方格左上角的列号 35. * size ：size = 2^k 棋盘规格为2^k*2^k 36. */

37. void ChessBoard(int tr,int tc,int dr,int dc,int size) 38. {

39. if(size == 1) 40. {

41. return; 42. }

43. int t = tile++;//L型骨牌编号 44. int s = size/2;//分割棋盘 45.

46. //覆盖左上角子棋盘

47. if(dr

49. ChessBoard(tr,tc,dr,dc,s); 50. }

51. else//特殊方格不在此棋盘中 52. {

53. //用编号为t的骨牌覆盖右下角 54. Board[tr+s-1][tc+s-1] = t; 55. //覆盖其余方格

56. ChessBoard(tr,tc,tr+s-1,tc+s-1,s); 57. } 58.

59. //覆盖右上角子棋盘

60. if(dr=tc+s)//特殊方格在此棋盘中 61. {

62. ChessBoard(tr,tc+s,dr,dc,s); 63. }

64. else//特殊方格不在此棋盘中 65. {

66. //用编号为t的骨牌覆盖左下角 67. Board[tr+s-1][tc+s] = t; 68. //覆盖其余方格

69. ChessBoard(tr,tc+s,tr+s-1,tc+s,s); 70. } 71.

72. //覆盖左下角子棋盘

73. if(dr>=tr+s && dc

75. ChessBoard(tr+s,tc,dr,dc,s); 76. }

77. else//特殊方格不在此棋盘中 78. {

79. //用编号为t的骨牌覆盖右上角 80. Board[tr+s][tc+s-1] = t; 81. //覆盖其余方格

82. ChessBoard(tr+s,tc,tr+s,tc+s-1,s); 83. } 84.

85. //覆盖右下角子棋盘

86. if(dr>=tr+s && dc>=tc+s)//特殊方格在此棋盘中 87. {

88. ChessBoard(tr+s,tc+s,dr,dc,s); 89. }

90. else//特殊方格不在此棋盘中 91. {

92. //用编号为t的骨牌覆盖左上角 93. Board[tr+s][tc+s] = t; 94. //覆盖其余方格

95. ChessBoard(tr+s,tc+s,tr+s,tc+s,s); 96. } 97. 98. }

程序运行结果如下：