棋盤覆寫問題——分治法-有解無憂

問題描述

有一個 $2^k$ x $2^k$ （k>0）的棋盤，恰好有一個方格與其他方格不同，稱之為特殊方格，現在要用如下圖所示的L形骨牌覆寫除了特殊方格以外的其他全部方格，骨牌可以任意旋轉，并且任何兩個骨牌不能重復，請給出一種覆寫方式，

樣例：

輸入：

輸出：

思路——分治法：

將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同，

遞回地解決這些子問題，然后將各個子問題的解合并得到原問題的解，

就是將規模為n的問題自頂向下分解，直到小問題分解到足夠小，可以解決時，再自底向上合并，從而得到原來的解，

當k=0（棋盤只有1格），特殊點只能唯一，L骨牌數為0

當k >0，則可將 2*kⅹ2*k 棋盤分割為 4個 2*k-1ⅹ2*k-1 的子棋盤

判斷特殊點在哪一個子棋盤中，用一塊L骨牌放在其它三個子棋盤的連接處

以此類推，則最后可將每個子棋盤劃分為1格的棋盤，結束遞回

代碼實作：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int arr[1000][1000];
 7 int num = 0;
 8 void ChessBoard(int x, int y, int a, int b, int length);
 9 
10 int main() {
11     //棋盤大小
12     int length;
13     cout << "請輸入length：" ;
14     cin >> length;
15 
16     //空白點坐標
17     int a, b;
18     cout << "請輸入空格位置：";
19     cin >> a >> b;
20     cout << endl;
21 
22     arr[a][b] = 0;//標點用0表示
23     ChessBoard(1, 1, a, b, length);
24     for (int i = 1; i <= length; i++) {
25         for (int j = 1; j <= length; j++) {
26             cout << arr[i][j] << "   ";
27         }
28         cout << endl;
29     }
30     return 0;
31 }
32 
33 void ChessBoard(int x, int y, int a, int b, int length) {
34     if (length == 1) {
35         return;
36     }
37     int h = length / 2;//分割棋盤
38     int t = ++num;//骨牌號，從1開始,相同數字代表是同一塊
39 
40     //以“田”的左下角為（1,1）
41     //左下角
42     if (a < x + h && b < y + h) {
43         ChessBoard(x, y, a, b, h);
44     }
45     else {
46         arr[x + h - 1][y + h - 1] = t;
47         ChessBoard(x, y, x + h - 1, y + h - 1, h);
48     }
49 
50     //左上角
51     if (a < x + h && b >= y + h) {
52         ChessBoard(x, y + h, a, b, h);
53     }
54     else {
55         arr[x + h - 1][y + h] = t;
56         ChessBoard(x, y + h, x + h - 1, y + h, h);
57     }
58 
59     //右下角
60     if (a >= x + h && b < y + h) {
61         ChessBoard(x + h, y, a, b, h);
62     }
63     else {
64         arr[x + h][y + h - 1] = t;
65         ChessBoard(x + h, y, x + h, y + h - 1, h);
66     }
67 
68     //右上角
69     if (a >= x + h && b >= y + h) {
70         ChessBoard(x + h, y + h, a, b, h);
71     }
72     else {
73         arr[x + h][y + h] = t;
74         ChessBoard(x + h, y + h, x + h, y + h, h);
75     }
76 }

參考資料：《計算機演算法設計與分析（第四版）》

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551222.html

標籤：其他

上一篇：[白嫖]阿里云服務器ECS以及無影云桌面

下一篇：返回列表