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

目录

一、题目

二、样例

三、示例代码

四、精简代码

五、总结

---

 

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

一、题目

 

输入格式：

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

第二行，两个整数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型骨，其牌号为tileint 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 subboardsoffsets = ((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 += 1if 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] = -1cover(board)for row in board:print((" %2i"*8)%tuple(row))3  3  4  4  8  8  9  93  2  2  4  8  7  7  95  2  6  6 10 10  7 115  5  6  1  1 10 11 1113 13 14  1 18 18 19 1913 12 14 14 18 17 17 1915 12 12 16 20 17 21 2115 15 16 16 20 20 21 -1

五、总结

还得练。