题解 P5461 【赦免战俘】
ShineEternal
2019-07-14 18:45:27
~~来一篇题解纪念一下~~
# 分析:
这道题其实是利用了分治的思想,我们可以利用函数递归实现。
每次函数传进去三个参数:当前矩阵左上角的坐标(x,y)和矩阵长度。
这样的话就能表示矩阵。
然后把左上角处理一下,其他部分接着递归即可。
> code
```cpp
#include<cstdio>
#include<cmath>
using namespace std;
int a[1200][1200];
int pd(int x,int y,int c)
{
if(c==1)return 0;
if(c==0)return 0;
for(int i=x;i<=x+c/2-1;i++)
{
for(int j=y;j<=y+c/2-1;j++)
{
a[i][j]=1;
}
}
pd(x+c/2,y,c/2);
pd(x,y+c/2,c/2);
pd(x+c/2,y+c/2,c/2);
return 0;
}
int main()
{
//freopen("testb.out","w",stdout);
int n;
scanf("%d",&n);
int tmp;
tmp=pow(2,n);
//printf("%d\n",tmp);
pd(1,1,tmp);
for(int i=1;i<=tmp;i++)
{
if(a[i][1]==1)printf("0");
else
printf("1");
for(int j=2;j<=tmp;j++)
{
if(a[i][j]==1)printf(" 0");
else
printf(" 1");
}
printf("\n");
}
return 0;
}
```