【AtCoder】ABC 357 C - Sierpinski carpet | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 371

問題概要

非負整数 $K$ に対して、以下のように「レベル $K$ のカーペット」を定義する。

$K = 0$ のとき、カーペットは黒いマス1個のみからなる $1 \times 1$ のグリッドである。
のとき、カーペットはのグリッドであり、このグリッドをのブロック9個に分割したとき、
- 中央のブロックはすべて白いマスからなる。
- 他の8個のブロックはレベル $(K-1)$ のカーペットである。

黒いマスを#、白いマスを.として、非負整数 $N$ に対してレベル $N$ のカーペットを出力せよ。

制約

$N$ は整数。
$0 \leq N \leq 6$

考察

サンプルケース2を見るとピンとくるかもしれないが、このカーペットはフラクタル図形のように見える。実際、問題のタイトルにあるように「シェルピンスキーのギャスケット」というフラクタル図形が存在する。

フラクタル図形というと、実装には再帰関数を使うのがよさそう。コードでは、カーペットをstringの1次元配列v、今考えているカーペットのレベルをlevel、v中での各ブロックの左上の行と列のインデックスをx, y、グリッドの1辺のマスの数をsizeとして、それらを引数に持つf()という再帰関数を作成し、以下のような処理を行っている。

はじめはvの全てのマスを' 'にする。
level == 0ならば、v[x][y]を黒色にする。
そうでなければ、sizeを3で割った後にで二重ループすることで、レベルのカーペットの各ブロックの中について考える。
- $i = j = 1$ のとき、1辺がsizeである中央のブロックについて考えているので、すべて白色にする。
- そうでないとき、このブロックはレベル $(\textrm{level} - 1)$ のカーペットそのものなので、レベルを1下げ、位置とサイズを適切に設定したうえでf()を呼び出し、再帰に入る。

再帰関数を使うと入れ子構造になって処理の全体像が見にくくなりがちだと私は思うのだが、こうやって考えてみると、問題文の要求を再帰関数を使うことで「そのまま」実装しているだけ、ということになる。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

void f(vector<string> &v, int level, int x, int y, int size)
{
    if (level == 0)
    {
        v[x][y] = '#';
    }
    else
    {
        size /= 3;
        rep(i, 0, 3) rep(j, 0, 3)
        {
            if (i == 1 && j == 1)
            {
                rep(dx, 0, size) rep(dy, 0, size)
                {
                    v[x + i * size + dx][y + j * size + dy] = '.';
                }
            }
            else
            {
                f(v, level - 1, x + i * size, y + j * size, size);
            }
        }
    }
}

int main()
{
    int N;
    cin >> N;
    int size = pow(3, N);
    vector<string> v(size, string(size, ' '));

    f(v, N, 0, 0, size);

    for (auto &&row : v)
    {
        for (auto &&c : row)
        {
            cout << c;
        }
        cout << endl;
    }

    return 0;
}