题解 P5461 【赦免战俘】
Uichiha_Itachi
2019-07-14 18:42:27
这题正解递归，歪解......一堆。
这里介绍一种比较简单的用循环模拟递归的写法。
我们发现给的这个图是自相似图形，（其实是斜过来的谢尔宾斯基三角形有损压缩的结果？）所以我们可以通过一个数组记录一个模式，并将其复制3次，加上左上角的全0正方形构成新的模式，如此迭代生成解。
详见代码：
```
#include <bits/stdc++.h>
using namespace std;
int d[1025][1025];
int pattern[1025][1025] = {{0,0},{0,1}};
int main()
{
int p;
cin >> p;
//核心部分
for(int i = 1;i <= p;i++)
{
int t = pow(2,i - 1);
for(int j = 1;j <= t;j++)
{
for(int k = 1;k <= t;k++)
{
d[j][k] = 0;
d[j + t][k] = d[j][k + t] = d[j + t][k + t] = pattern[j][k];
}
}
for(int j = 1;j <= t * 2;j++)
{
for(int k = 1;k <= t * 2;k++)
{
pattern[j][k] = d[j][k];
//printf("%d,%d,%d'\n",j,k,t);
}
}
}
int s = pow(2,p);
for(int i = 1;i <= s;i++)
{
for(int j = 1;j <= s - 1;j++)
{
cout << d[i][j] << " ";
}
cout << d[i][s] << endl;
}
return 0;
}
```