题解：B2163 棋盘覆盖

zhonggong · 2025-10-12 10:59:28 · 题解

题目传送门。

样例：

就是这张图片。

我们可以使用一个递归函数，把棋盘分成 4 份，每次判断特殊方格在哪里，递归调用就可以了。注意，在棋盘大小是 2 \times 2 时，要提前跳出，要不然会无限递归下去。

代码：

#include <iostream>
using namespace std;
int a[1025][1025],cnt;
void f(int x1,int y1,int x2,int y2,int x,int y) //递归函数
{
    if(x1==x2-1) //提前跳出
    {
        ++cnt;
        int t=a[x][y];
        a[x1][y1]=cnt;
        a[x1][y2]=cnt;
        a[x2][y1]=cnt;
        a[x2][y2]=cnt;
        a[x][y]=t;
        return;
    }
    int mx=(x1+x2)/2,my=(y1+y2)/2;
    if((x<=mx)&&(y<=my)) //特殊方格在第一象限
    {
        f(x1,y1,mx,my,x,y); //先递归调用这一部分
        ++cnt;
        a[mx][my+1]=cnt; //中间的“L”
        a[mx+1][my]=cnt;
        a[mx+1][my+1]=cnt;
        f(mx+1,y1,x2,my,mx+1,my); //然后再调用其他部分
        f(x1,my+1,mx,y2,mx,my+1);
        f(mx+1,my+1,x2,y2,mx+1,my+1);
    }
    if((x>mx)&&(y<=my)) //特殊方格在第二象限
    {
        f(mx+1,y1,x2,my,x,y); //先递归调用这一部分
        ++cnt;
        a[mx][my]=cnt; //中间的“L”
        a[mx][my+1]=cnt;
        a[mx+1][my+1]=cnt;
        f(x1,y1,mx,my,mx,my); //然后再调用其他部分
        f(x1,my+1,mx,y2,mx,my+1);
        f(mx+1,my+1,x2,y2,mx+1,my+1);
    }
    if((x<=mx)&&(y>my)) //特殊方格在第三象限
    {
        f(x1,my+1,mx,y2,x,y); //先递归调用这一部分
        ++cnt;
        a[mx][my]=cnt; //中间的“L”
        a[mx+1][my]=cnt;
        a[mx+1][my+1]=cnt;
        f(x1,y1,mx,my,mx,my); //然后再调用其他部分
        f(mx+1,y1,x2,my,mx+1,my);
        f(mx+1,my+1,x2,y2,mx+1,my+1);
    }
    if((x>mx)&&(y>my)) //特殊方格在第四象限
    {
        f(mx+1,my+1,x2,y2,x,y); //先递归调用这一部分
        ++cnt;
        a[mx][my]=cnt; //中间的“L”
        a[mx][my+1]=cnt;
        a[mx+1][my]=cnt;
        f(x1,y1,mx,my,mx,my); //然后再调用其他部分
        f(mx+1,y1,x2,my,mx+1,my);
        f(x1,my+1,mx,y2,mx,my+1);
    }
}
int main()
{
    int k,x,y,n=1;
    cin>>k>>x>>y;
    for(int i=1;i<=k;++i) //这样更方便
        n*=2;
    f(1,1,n,n,x,y);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}