洛谷 P1911 L国的战斗之排兵布阵 题解【递归】【分治】

点击量：232

    灵活的分治思想。

目录

题目背景

L国即将与I国发动战争！！

题目描述

L国的指挥官想让他的每一个军营都呈现出国徽形——“L”形（方向无所谓）。当然，他的指挥营除外（这叫做个性），他想不出该怎么排，就这样，这任务又变成了你的……

输入输出格式

输入格式：

一行三个数：n、x、y表示军营大小为2^N，指挥营在(x,y)的位置上。

 

输出格式：

2^N行，每行2^N个数，表示军营号（按先行后列顺序）指挥营用0表示。

 

输入输出样例

输入样例#1：

4 1 3

输出样例#1：

1 1 0 2 3 3 4 4 5 5 6 6 7 7 8 8
1 9 2 2 3 10 10 4 5 11 11 6 7 12 12 8
13 9 9 14 15 15 10 16 17 11 18 18 19 19 12 20
13 13 14 14 21 15 16 16 17 17 18 22 22 19 20 20
23 23 24 21 21 25 26 26 27 27 28 28 22 29 30 30
23 31 24 24 25 25 32 26 27 33 33 28 29 29 34 30
35 31 31 36 37 32 32 38 39 39 33 40 41 34 34 42
35 35 36 36 37 37 38 38 43 39 40 40 41 41 42 42
44 44 45 45 46 46 47 43 43 48 49 49 50 50 51 51
44 52 52 45 46 53 47 47 48 48 54 49 50 55 55 51
56 52 57 57 58 53 53 59 60 54 54 61 62 62 55 63
56 56 57 64 58 58 59 59 60 60 61 61 65 62 63 63
66 66 67 64 64 68 69 69 70 70 71 65 65 72 73 73
66 74 67 67 68 68 75 69 70 76 71 71 72 72 77 73
78 74 74 79 80 75 75 81 82 76 76 83 84 77 77 85
78 78 79 79 80 80 81 81 82 82 83 83 84 84 85 85

说明

数据范围：

1≤n≤10, 1≤x,y≤2^n

题解：

    第一眼看上去，很难联想到这是个分治题。不过，我们把数据缩小会发现，当只有2×2的格子时，因为0号格子是固定的，所以剩下一个L的形状也是固定的。再把它放大，如果这是一个4×4的格子中的四分之一，那么会剩下一个更大的L型。我们需要想办法把这个L型变成和之前一样的2×2图形，才能继续解决这个问题。

    在左边的图形中，我们得到了一个大L形。可以很快地看出它的一个解，即右图。我们发现，如果要使另外三个2×2的正方形也出现刚才处理的情况，就得给它们制造出一个“0号点”，而这样的“0号点”也要互相成为L型。因此就是剩下的三个部分，每一部分出一个角落凑成一个L型。以此类推，当边长为$ 2^n$时，它的子正方形一定有一个的“0号点”是固定的，剩下的把“0号点”放在角落即可。俯瞰图大概是这样？：

    这样递归下去，每次判断孤立的那个“0号点”在哪就可以了。最后还要从前到后扫一遍答案。

Code：

#include<cstdio>
#include<cstring>
int cnt=0;
int a[1100][1100];
void divide(int lx,int ly,int rx,int ry,int x,int y)
{
    if(lx==rx&&ly==ry)
        return;
    int midx=lx+rx>>1,midy=ly+ry>>1;
    if(x<=midx&&y<=midy)//左上
    {
        a[midx][midy+1]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,x,y);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else if(x>midx&&y<=midy)//左下
    {
        a[midx][midy]=++cnt;
        a[midx][midy+1]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,x,y);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else if(x<=midx&&y>midy)//右上
    {
        a[midx][midy]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx+1][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,x,y);//右上
        divide(midx+1,midy+1,rx,ry,midx+1,midy+1);//右下
    }
    else//右下
    {
        a[midx][midy]=++cnt;
        a[midx+1][midy]=cnt;
        a[midx][midy+1]=cnt;
        divide(lx,ly,midx,midy,midx,midy);//左上
        divide(midx+1,ly,rx,midy,midx+1,midy);//左下
        divide(lx,midy+1,midx,ry,midx,midy+1);//右上
        divide(midx+1,midy+1,rx,ry,x,y);//右下
    }
}
int to[500000];
int main()
{
    memset(to,-1,sizeof(to));
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    divide(1,1,(1<<n),(1<<n),x,y);
    to[0]=0;
    int tcnt=0;
    for(int i=1;i<=(1<<n);i++)
    {
        for(int j=1;j<=(1<<n);j++)
        {
            if(to[a[i][j]]==-1)
                to[a[i][j]]=++tcnt;
            printf("%d ",to[a[i][j]]);
        }
        puts("");
    }
    return 0;
}