Uchiha_Itachi 的博客

Uchiha_Itachi 的博客

题解 P5461 【赦免战俘】

posted on 2019-07-14 18:42:27 | under 题解 |

这题正解递归,歪解......一堆。

这里介绍一种比较简单的用循环模拟递归的写法。

我们发现给的这个图是自相似图形,(其实是斜过来的谢尔宾斯基三角形有损压缩的结果?)所以我们可以通过一个数组记录一个模式,并将其复制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;
}