【算法】棋盘覆盖问题源代码及精简版
目录
一、题目
二、样例
三、示例代码
四、精简代码
五、总结
对于棋盘覆盖问题的解答和优化。
一、题目
输入格式：
第一行，一个整数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五、总结
还得练。