题解 P5461 【赦免战俘】

邻叔丁基苯酚 · 2019-07-14 18:59:16 · 题解

思路：题目要求对一直对方阵分割，且每次分割的方式相同，子方阵的规格相同，显然用分治算法解决。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
LL a[5005][5005];//方阵。为方便，a[i][j]==0表示未赦免，a[i][j]==1表示赦免。
void absolve(LL x1,LL y1,LL x2,LL y2,LL len)//赦免的递归函数。
//(x1,y1)为方阵左上角的坐标，（x2,y2）为方阵右下角的坐标。
{
    for(LL i=x1;i<=(x1+x2)/2;++i)
        for(LL j=y1;j<=(y1+y2)/2;++j)
            a[i][j]=1;
    //方阵左上角的赦免。
    if(len==2){return;}//边界条件。如果是2*2的方阵，终止递归。
    absolve(x1,(y1+y2+1)/2,(x1+x2)/2,y2,len/2);//递归方阵的右上角。
    absolve((x1+x2+1)/2,y1,x2,(y1+y2)/2,len/2);//递归方阵的左下角。
    absolve((x1+x2+1)/2,(y1+y2+1)/2,x2,y2,len/2);//递归方阵的右下角。
}
int main()
{
    LL n,len;
    scanf("%lld",&n);
    len=1<<n;
    absolve(1,1,len,len,len);
    for(LL i=1;i<=len;++i)
    {
        for(LL j=1;j<=len;++j)
        {
            if(a[i][j]==1) printf("0 ");
            else if(a[i][j]==0) printf("1 ");
        }
        printf("\n");
    }
    return 0;
}

关于方阵递归参数的转移在草稿纸上算出即可。