目錄

一、題目

二、樣例

三、示例代碼

四、精簡代碼

五、總結(jié)

---

?

對于棋盤覆蓋問題的解答和優(yōu)化。

一、題目

?

輸入格式：

第一行，一個整數(shù)n（棋盤n*n，n確保是2的冪次，n<64）

第二行，兩個整數(shù)a和b, 特殊方格的位置，從左上開始計數(shù)a是列號（從1開始），b行號，從上到下，從1開始

?

輸出格式：

n*n個整數(shù)

每行n個數(shù)，從左上開始，一行一行輸出(最多8行），每個輸出對應的L型塊編號，輸出數(shù)據(jù)占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);    //將右下角作為特殊方格繼續(xù)處理該象限}//考慮右上角象限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);      //將左下角作為特殊方格繼續(xù)處理該象限}//處理左下角象限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);    //將右上角作為特殊方格繼續(xù)處理該象限}//處理右下角象限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);      //將左上角作為特殊方格繼續(xù)處理該象限}
}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");}
}

代碼較為繁瑣?？梢岳迷O置offset來進行優(yōu)化。

四、精簡代碼

在《Python Algorithms Mastering Basic Algorithms in the Python Language》里面有一段代碼，就是對上面代碼的精簡。在國內(nèi)各大網(wǎng)站都沒有看見。本人也是覺得很唏噓。

    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

五、總結(jié)

還得練。

?

?

?