首页 > 试题广场 >

(棋盘覆盖问题)在一个2k ×2ksu...

[填空题]
(棋盘覆盖问题)在一个2k ×2k 个方格组成的棋盘中恰有一个方格与其他方格不同(图中标记为-1的方格),称之为特殊方格。现用L型(占3个小格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到的纸片数恰好是(4k −1) / 3 。在下表给出的一个覆盖方案中,k=2,相同的3个数字构成一个纸片。 下面给出的程序是用分治法设计的,将棋盘一分为四,依次处理左上角、右上角、左下角、右下角,递归进行。请将程序补充完整。
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5

#include "stdio.h"
int board[65][65], tile; /* tile 为纸片编号*/
void chessboard(int tr, int tc, int dr, int dc, int size)
/* dr,dc依次为特殊方格的行、列号 */
{
    int t, s;
    if (size == 1)
    1;
    t = tile++;
    s = size / 2;
    if (   2  )
    chessboard(tr, tc, dr, dc, s);
    else
    {
        board[tr + s - 1][tc + s - 1] = t;
        3;
    }
    if (dr < tr + s && dc >= tc + s)
        chessboard(tr, tc + s, dr, dc, s);
    else {
        board[tr + s - 1][tc + s] = t;
        4;
    }
    if (dr >= tr + s && dc < tc + s)
        chessboard(tr + s, tc, dr, dc, s);
    else {
        board[tr + s][tc + s - 1] = t;
        5;
    }
    if (dr >= tr + s && dc >= tc + s)
        chessboard(tr + s, tc + s, dr, dc, s);
    else {
        board[tr + s][tc + s] = t;
        6;
    }
}
void prt1(int b[][65], int n) {
    int i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++)
            printf("%3d", b[i][j]);
        printf("\n");
    }
}
int main(void) {
    int size, dr, dc;
    printf("input size(4/8/16/64):\n");
    scanf("%d", &size);
    printf("input the position of special block(x,y):\n");
    scanf("%d%d", &dr, &dc);
    board[dr][dc] = -1;
    tile++;
    chessboard(1, 1, dr, dc, size);
    prt1(board, size);
} 

这道题你会答吗?花几分钟告诉大家答案吧!