B2163 题解

题目思路

我们发现，如果直接对大棋盘填充骨牌，则很容易多填、漏填，或是在填充最后几个骨牌时发现前面填错了而要推倒重来，非常麻烦。

不妨先从最简单的

2 ^ 1 \times 2 ^ 1

棋盘开始考虑。此时有一个特殊方格无法放置骨牌，剩下的三个格子正好可以放下一个骨牌，若用

0

表示特殊方格，则有以下四种情况。

四种不同的情况如表格所示
情况 $0$ ，左上角为特殊方格			情况 $1$ ，右上角为特殊方格
$0$	$1$	$1$	$0$
$1$	$1$	$1$	$1$
情况 $2$ ，左下角为特殊方格			情况 $3$ ，右下角为特殊方格
$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$

我们考虑推广这种最简单的情况。对于

2 ^ 2 \times 2 ^ 2

的棋盘，我们会想到把它分成四块

2 ^ 1 \times 2 ^ 1

的棋盘，因为这种情况我们会做。对于四块小棋盘，有一块是原本就有特殊方格的棋盘，可以直接套用上述做法。对于剩下三块小棋盘，它们也组成了一个标准的骨牌，只是长宽都放大为了原来的

2

倍。

此时我们希望把这三块小棋盘也套用上述做法，那么就需要人为构造出三个的特殊方格，也就是提前放置一个骨牌占用三个格子。对于这个提前放置的骨牌，我们不难想到在大棋盘的四个中心位置放置骨牌，除去包含特殊方格的小棋盘，正好剩余三个中心位置，由上述表格知它们一定连通。

进一步的，我们可以把

2 ^ k \times 2 ^ k

的大棋盘分成四块

2 ^ {k - 1} \times 2 ^ {k - 1}

的小棋盘，其中有一块是原本就有特殊方格的棋盘，可以直接套用上述做法。对于剩下三块小棋盘，我们可以提前放置一个骨牌之后套用上述做法。那么下一步就是把每个

2 ^ {k - 1} \times 2 ^ {k - 1}

的棋盘分为四个更小的棋盘……

就这样，我们写一个递归函数，分治地解决每个子问题，这道题就做完了。

题目代码

本题的分治需要考虑四种情况，为了方便写代码，我舍弃了更小常数的暴力推导，而是通过不同的函数处理一部分结果，让剩下的部分可以用循环完成，这样代码就变简单了很多。

代码中的四个区域编号划分与上述表格相同，可对照理解。

CPP

int k;
int ans[1055][1055];
int n;
int spx , spy;
int cnt;
struct four // 存储一个大棋盘的四个中心位置的坐标
{
    pair < int , int > a[4];
    four()
    {
        a[0].first = a[0].second = -1;
        a[1] = a[2] = a[3] = a[0];
    }
};
int check(int a , int b , int l , int x , int y); // 左上角为 (a , b)，边长为 l，特殊点为 (x , y) 时计算特殊点所在区域
four get(int a , int b , int l , int type); // 左上角为 (a , b)，边长为 l，特殊点所在区域为 type 时计算棋盘的四个中心位置
void solve(int a , int b , int l , int x , int y) // 左上角为 (a , b)，边长为 l，特殊点为 (x , y) 时递归构造答案
{
    if(l == 1)
    {
        return ;
    }
    int type = check(a , b , l , x , y);
    four put = get(a , b , l , type);
    cnt++;
    for(int i = 0 ; i <= 3 ; i++)
    {
        if(type != i) // 只要当前的中心位置不是特殊点所在的位置，就可以提前放置骨牌
        {
            ans[put.a[i].first][put.a[i].second] = cnt;
        }
    }
    for(int i = 0 ; i <= 3 ; i++)
    {
        int stx = a + (i & 1) * (l / 2); // 通过上述表格结合理解，推导出左上角坐标的计算公式
        int sty = b + (i >> 1) * (l / 2);
        if(type == i)
        {
            solve(stx , sty , l / 2 , x , y);
        }
        else
        {
            solve(stx , sty , l / 2 , put.a[i].first , put.a[i].second);
        }
    }
}
signed main()
{
    read(k , spx , spy);
    n = 1 << k;
    memset(ans , -1 , sizeof(ans));
    ans[spx][spy] = 0;
    solve(1 , 1 , n , spx , spy);
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            print(ans[i][j] , " \n" [j == n]);
        }
    }
	return 0;
}
int check(int a , int b , int l , int x , int y)
{
    int midx = a + l / 2 - 1;
    int midy = b + l / 2 - 1;
    bool ax = (x > midx) , ay = (y > midy);
    if(!ax && !ay) { return 0; } // 此处的区域编号及划分可参考上述表格理解
    else if(ax && !ay) { return 1; }
    else if(!ax && ay) { return 2; }
    else { return 3; }
}
four get(int a , int b , int l , int type)
{
    int midx = a + l / 2 - 1;
    int midy = b + l / 2 - 1;
    pair < int , int > pa , pb , pc , pd;
    pa = make_pair(midx , midy);
    pb = make_pair(midx + 1 , midy);
    pc = make_pair(midx , midy + 1);
    pd = make_pair(midx + 1 , midy + 1);
    four ans; // 把 type 位置空出来不用赋值，这样舍弃更优的空间，但可以直接使用循环做
    if(type == 0) { ans.a[1] = pb , ans.a[2] = pc , ans.a[3] = pd; }
    if(type == 1) { ans.a[0] = pa , ans.a[2] = pc , ans.a[3] = pd; }
    if(type == 2) { ans.a[0] = pa , ans.a[1] = pb , ans.a[3] = pd; }
    if(type == 3) { ans.a[0] = pa , ans.a[1] = pb , ans.a[2] = pc; }
    return ans;
}

题解：B2163 棋盘覆盖

文章操作

B2163 题解

题目思路

题目代码

相关推荐

评论

题解：B2163 棋盘覆盖