分治法之棋盘覆盖

佚名 5年前 (2019-11-25) 算法 2112人围观抢沙发百度已收录

利用分治思想实现一个棋牌覆盖的简单程序，以复习分治法的内容。

 1 #include<iostream>
 2 #include<cmath>
 3 
 4 using namespace std;
 5 
 6 #define n 4
 7 int tile = 0;
 8 
 9 int board[n][n];
10 
11 void ChessBoardCover(int tr, int tc, int dr, int dc, int size);
12 
13 
14 int main()
15 {
16     int a, b;
17     cout << "Input the position of the special check:" << endl;
18     cin >> a >> b;
19 
20     ChessBoardCover(0,0,a,b,n);
21 
22     cout << "Output the chessboard(0 represents the special one):" << endl;
23     for (int i = 0; i < n; i++)
24     {
25         for (int j = 0; j < n; j++)
26             cout << board[i][j] << " ";
27         cout << endl;
28     }
29     getchar();
30     getchar();
31 }
32 
33 /*
34 tile是一个全局整形变量，用来表示L形骨牌的编号，初始值为0。
35 tr：棋盘左上角方格的行号；
36 tc：棋盘左上角方格的列号；
37 dr：特殊方格所在的行号；
38 dc：特殊方格所在的列号；
39 size：size = 2^k，棋盘规格为2^k×2^k
40 */
41 void ChessBoardCover(int tr, int tc, int dr, int dc, int size)
42 {
43     if (size == 1)
44         return;
45     int t = ++tile;  // L型骨牌号
46     int    s = size / 2;  // 分割棋盘
47 
48     // 覆盖左上角子棋盘
49     if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中
50         ChessBoardCover(tr, tc, dr, dc, s);
51     else 
52     {// 此棋盘中无特殊方格
53         board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角
54         ChessBoardCover(tr, tc, tr + s - 1, tc + s - 1, s); // 覆盖其余方格
55     }
56 
57     // 覆盖右上角子棋盘
58     if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中
59         ChessBoardCover(tr, tc + s, dr, dc, s);
60     else {// 此棋盘中无特殊方格
61         board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角
62                                        // 覆盖其余方格
63         ChessBoardCover(tr, tc + s, tr + s - 1, tc + s, s);
64     }
65 
66     // 覆盖左下角子棋盘
67     if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中
68         ChessBoardCover(tr + s, tc, dr, dc, s);
69     else
70     {
71         // 用 t号L型骨牌覆盖右上角
72         board[tr + s][tc + s - 1] = t; 
73         
74         // 覆盖其余方格
75         ChessBoardCover(tr + s, tc, tr + s, tc + s - 1, s);
76     }
77 
78     // 覆盖右下角子棋盘
79     if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中
80         ChessBoardCover(tr + s, tc + s, dr, dc, s);
81     else
82     {
83         board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角
84         ChessBoardCover(tr + s, tc + s, tr + s, tc + s, s); // 覆盖其余方格
85     }
86 }