棋盤覆寫問題

題意：有一個(1<<k)*(1<<k)的方格棋盤，恰有一個方格是黑色的，其他為白色，你的任務是用包含3個方格的L型牌覆寫所有白色方格。

思路：分治法。

1 #include<iostream>  
 2 using namespace std;
 3 int board[1025][1025];
 4 int num = 0;
 5 
 6 void ChessBoard(int tr, int tc, int dr, int dc, int size)
 7 {
 8     if (size == 1) return;//遞歸邊界   
 9     int ans = ++num;
10     int s = size / 2;   //分割棋盤
11 
12     //處理左上角
13     if (tr + s - 1 >= dr && tc + s - 1 >= dc)  //有黑塊
14     {
15         ChessBoard(tr, tc, dr, dc, s);
16     }
17     else                               //沒有黑塊
18     {
19         board[tr + s - 1][tc + s - 1] = ans;
20         ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
21 
22     }
23 
24     //處理右上角
25     if (tr + s - 1 >= dr && tc + s <= dc)
26     {
27         ChessBoard(tr, tc + s, dr, dc, s);
28     }
29     else
30     {
31         board[tr + s - 1][tc + s] = ans;
32         ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
33     }
34 
35     //處理左下角
36     if (tr + s <= dr && tc + s - 1 >= dc)
37     {
38         ChessBoard(tr + s, tc, dr, dc, s);
39     }
40     else
41     {
42         board[tr + s][tc + s-1] = ans;
43         ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
44     }
45 
46     //處理右下角
47     if (tr + s <= dr && tc + s <= dc)
48     {
49         ChessBoard(tr + s, tc + s, dr, dc, s);
50     }
51     else
52     {
53         board[tr + s][tc + s] = ans;
54         ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
55     }
56 }
57 
58 int main()
59 {
60     int i, j;
61     int k;
62     while (cin >> k)
63     {
64         int size = 1 << k;   //邊長
65         int x, y;
66         cin >> x >> y;
67         board[x][y] = 0;    //将黑塊記錄為0
68         ChessBoard(1, 1, x, y, size);
69         for (i = 1; i <= size; i++)
70         {
71             for (j = 1; j <= size; j++)
72                 cout << board[i][j] << " ";
73             cout << endl;
74         }
75     }
76     return 0;
77 }