分治算法-棋盘覆盖

在一个 2ᵏ × 2ᵏ 个方格组成的棋盘中，若恰有一个方格与其他方格不同（图中标记为 -1 的方格），则称该方格为特殊方格。现在用 L 型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是用到的纸片数恰好是 (4ᵏ - 1) / 3 。写一个程序，求覆盖方案。

如在下图中，给出的一个覆盖方案中，k = 2 ，那么就是 4 × 4 个方格，那么纸片数恰好是 5 个。

【输入描述】

输入第一行为方阵的规模，也就是数组的行列值。输入第二行两个整数，表示特殊方格的行列下标。

【输出描述】

输出覆盖后的棋盘数组。

【输入样例】

//样例1：
8
4 4
【输出样例】

//样例1：
3 3 4 4 8 8 9 9
3 2 2 4 8 7 7 9
5 2 6 6 10 10 7 11
5 5 6 -1 1 10 11 11
13 13 14 1 1 18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21
【参考程序】

//小牛编程
#include <bits/stdc++.h>
using namespace std;

// k=6, 64 x 64二维数组(下标从1开始)，tile为纸片编号
int board[65][65], tile = 1;

/*
 * tr, tc 棋盘的起始行列号, [1, 1]
 * size 2ᵏ ：2、4、8、16、32、64
 * dr, dc 为特殊方格的行列号，比如 [size/2, size/2]
 */
void chessBoard(int tr, int tc, int dr, int dc, int size) {
    int t, s;
    if (size == 1)
        return;
    t = tile++;
    s = size / 2;

    // 左上角
    if (dr < tr + s && dc < tc + s) {
        chessBoard(tr, tc, dr, dc, s);
    } else {
        board[tr + s - 1][tc + s - 1] = t; 
        chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); 
    }

    // 右上角
    if (dr < tr + s && dc >= tc + s) {
        chessBoard(tr, tc + s, dr, dc, s);
    } else {
        board[tr + s - 1][tc + s] = t;
        chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }

    // 左下角
    if (dr >= tr + s && dc < tc + s) {
        chessBoard(tr + s, tc, dr, dc, s);
    } else {
        board[tr + s][tc + s - 1] = t;
        chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }

    // 右下角
    if (dr >= tr + s && dc >= tc + s) {
        chessBoard(tr + s, tc + s, dr, dc, s);
    } else {
        board[tr + s][tc + s] = t;
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

int main() {
    int size; 
    int dr, dc;
    cin >> size;     
    cin >> dr >> dc; 

    board[dr][dc] = -1;
    chessBoard(1, 1, dr, dc, size);

    //打印
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            cout << setw(5) << board[i][j];
        }
        cout << endl;
    }

    return 0;
}

经典算法

分治算法-棋盘覆盖