本文主要是介绍棋盘覆盖问题 (10 分)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Description

用分治法求解棋盘覆盖问题。有一个2k×2k（k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下的L型骨牌覆盖除了特殊方格外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重叠。请给出一种覆盖方法。

Input

第一行输入一个数n表示棋盘大小，第二行输入特殊方格的行列下标。

8
1 2

Output

输出棋盘。

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

Solution

呃，其实直接输出样例就过了，数据水的一批

这是一个分治问题，首先能想到将大棋盘不断分为一半来进行处理。

对于子问题的棋盘，其格子数必为 2 的次方，当然 1 直接返回即可，但是每一个骨牌是 3 个格子，那么其必须有一个格子是被放置过的。

因为一开始就有一个特殊方格，所以只需要将一个骨牌的三个格子，分别放到子棋盘上即可铺满整个棋盘。这么说不好理解，就比如下图：

好像画的不是很好，能看懂就行~

就一直递归做下去，直到格子数为 1 返回，然后你就会发现最终棋盘就被铺满了。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1100;
int c;
int n,a,b,h;
int q[N][N];
int get(int x)
{
    return (to_string(x)).size();
}
void DrawBox(int row,int col,int x,int y,int sz)
{
    if(sz == 1) return ;
    int leng = sz / 2;
    int t = ++ c;
    int center_row = row + leng;
    int center_col = col + leng;
    // 左上角
    if(x < center_row && y < center_col) // 在左上角
    {
        DrawBox(row,col,x,y,leng);
    }
    else
    {
        q[center_row-1][center_col-1] = t;
        DrawBox(row,col,center_row-1,center_col-1,leng);
    }
    // 右上角
    if(x < center_row && y >= center_col)
    {
        DrawBox(row,center_col,x,y,leng);
    }
    else
    {
        q[center_row-1][center_col] = t;
        DrawBox(row,center_col,center_row-1,center_col,leng);
    }
    // 左下角
    if(x >= center_row && y < center_col)
    {
        DrawBox(center_row,col,x,y,leng);
    }
    else
    {
        q[center_row][center_col-1] = t;
        DrawBox(center_row,col,center_row,center_col-1,leng);
    }
    // 右下角
    if(x >= center_row && y >= center_col)
    {
        DrawBox(center_row,center_col,x,y,leng);
    }
    else
    {
        q[center_row][center_col] = t;
        DrawBox(center_row,center_col,center_row,center_col,leng);
    }
}
int main()
{
    cin >> n >> a >> b;
    a ++ ; b ++ ;
    q[a][b] = 1;
    DrawBox(1,1,a,b,n);
    q[a][b] = 0;
    for (int i = 1 ; i <= n ; i ++ )
    {
        for (int j = 1 ; j <= n ; j ++ )
        {
            cout << q[i][j];
            h = get(q[i][j]);
            for (int k = 1 ; k <= 5 - h ; k ++ ) cout << ' ';
        }
        if(i != n) cout << endl;
    }
    return 0;
}

这篇关于棋盘覆盖问题 (10 分)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！