分治法棋盘覆盖c语言源代码

以下是一个基于分治法的棋盘覆盖算法的 C 代码：

#include <stdio.h>
#include <stdlib.h>

#define BOARD_SIZE 8

void chessboard_cover(int **board, int tr, int tc, int dr, int dc, int size, int label)
{
    if (size == 1) {
        return;
    }
    int s = size / 2;
    int t = label++;
    // 左上角
    if (dr < tr + s && dc < tc + s) {
        chessboard_cover(board, tr, tc, dr, dc, s, t);
    } else {
        board[tr + s - 1][tc + s - 1] = t;
        chessboard_cover(board, tr, tc, tr + s - 1, tc + s - 1, s, t);
    }
    // 右上角
    if (dr < tr + s && dc >= tc + s) {
        chessboard_cover(board, tr, tc + s, dr, dc, s, t);
    } else {
        board[tr + s - 1][tc + s] = t;
        chessboard_cover(board, tr, tc + s, tr + s - 1, tc + s, s, t);
    }
    // 左下角
    if (dr >= tr + s && dc < tc + s) {
        chessboard_cover(board, tr + s, tc, dr, dc, s, t);
    } else {
        board[tr + s][tc + s - 1] = t;
        chessboard_cover(board, tr + s, tc, tr + s, tc + s - 1, s, t);
    }
    // 右下角
    if (dr >= tr + s && dc >= tc + s) {
        chessboard_cover(board, tr + s, tc + s, dr, dc, s, t);
    } else {
        board[tr + s][tc + s] = t;
        chessboard_cover(board, tr + s, tc + s, tr + s, tc + s, s, t);
    }
}

void print_board(int **board)
{
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            printf("%d\t", board[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int **board = (int **)malloc(sizeof(int *) * BOARD_SIZE);
    for (int i = 0; i < BOARD_SIZE; i++) {
        board[i] = (int *)malloc(sizeof(int) * BOARD_SIZE);
        for (int j = 0; j < BOARD_SIZE; j++) {
            board[i][j] = 0;
        }
    }
    int dr = 6, dc = 4; // 特殊方格的坐标
    int label = 1; // 特殊方格的标签
    chessboard_cover(board, 0, 0, dr, dc, BOARD_SIZE, label);
    print_board(board);
    for (int i = 0; i < BOARD_SIZE; i++) {
        free(board[i]);
    }
    free(board);
    return 0;
}

这个算法的时间复杂度是 $O(n^2)$，其中 $n$ 是棋盘的大小。