【算法】棋盘覆盖问题源代码及精简版

对于棋盘覆盖问题的解答和优化。

一、题目

输入格式：

第一行，一个整数n（棋盘n*n，n确保是2的幂次，n<）

第二行，两个整数a和b, 特殊方格的位置，从左上开始计数a是列号（从1开始），b行号，从上到下，从1开始

输出格式：

n*n个整数

每行n个数，从左上开始，一行一行输出(最多8行），每个输出对应的L型块编号，输出数据占4位，不足前面补空格。

编号是递归从左上、右上、右下到左下的顺序进行。如下

二、样例

输入样例：

8

2 3

输出样例：

   3   3   4   4   8   8   9   9
   3   2   0   4   8   7   7   9
   5   2   2   6  10  10   7  11
   5   5   6   6   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<stdio.h>
#include <iostream>
using namespace std;

#define MAX 1025
//问题表示
int k;                            //棋盘大小
int x,y;                        //特殊方格的位置
int board[MAX][MAX];
int tile=1;                                    //L型骨牌的编号,从1开始
void ChessBoard(int tr,int tc,int dr,int dc,int size) {
    if(size==1) return;                        //递归出口
    int t=tile++;                            //取一个L型骨，其牌号为tile
    int 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;                //用t号L型骨牌覆盖右下角
        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;                    //用t号L型骨牌覆盖左下角
        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;                  //用t号L型骨牌覆盖右上角
        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;                      //用t号L型骨牌覆盖左上角
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);      //将左上角作为特殊方格继续处理该象限
    }
}

int main() {
    int size;
    //size=8, x=3, y=6;
    cin>>size>>x>>y;
    x--, y--;
    ChessBoard(0, 0, x, y, size);
    for(int i=0; i<min(8, size); i++) {                //输出方案
        for(int j=0; j<size; j++)
            printf("%4d",board[i][j]);
        printf("\n");
    }
}

代码较为繁琐。可以利用设置offset来进行优化。

四、精简代码

在《Python Algorithms Mastering Basic Algorithms in the Python Language》里面有一段代码，就是对上面代码的精简。在国内各大网站都没有看见。本人也是觉得很唏嘘。

    def cover(board, lab=1, top=0, left=0, side=None):
        if side is None: side = len(board)

        # Side length 
        s = side // 2

        # Offsets for outer/inner squares of subboards
        offsets = ((0, -1), (side-1, 0))

        for dy_outer, dy_inner in offsets:
            for dx_outer, dx_inner in offsets:
            # If the outer corner is not set...
                if not board[top+dy_outer][left+dx_outer]:
                # ... label the inner corner: 
                    board[top+s+dy_inner][left+s+dx_inner] = lab


        # Next label: 
        lab += 1
        if s > 1:
            for dy in [0, s]:
                for dx in [0, s]:
                    # Recursive calls, if s is at least 2:
                    lab = cover(board, lab, top+dy, left+dx, s)

        # Return the next available label: 
        return lab

可以运行下面代码验证，可知是正确的。

    board = [[0]*8 for i in range(8)]
    board[7][7] = -1
    cover(board)
    for row in board:
        print((" %2i"*8)%tuple(row))

    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 18 18 19 19
   13 12 14 14 18 17 17 19
   15 12 12 16 20 17 21 21
   15 15 16 16 20 20 21 -1

五、总结

还得练。