Codeforces Round #141 Fractal Detector

問題概要

ある規則によって作成されるフラクタルが、与えられた平面上にいくつかるか数える。

方針

フラクタルかどうかは分割統治で判定できる。メモ化して高速化する。実装ややこしそうと思ったけど、以外と簡単に書けた。

ソースコード

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

string bd[512];
bool dp[1<<4][10][512][512];
int r, c;

int main() {
    cin >> r >> c;

    REP (i, r) cin >> bd[i];
    
    // base case
    for (int i = 0; i + 1 < r; i++) {
        for (int j = 0; j + 1 < c; j++) {
            int mask = 0;
            mask |= (bd[i][j] == '*');
            mask <<= 1;
            mask |= (bd[i][j+1] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j+1] == '*');
            dp[mask][1][i][j] = true;
        }
    }

    int size = 2;
    for (int k = 2; k < 10; k++) {
        size *= 2;
        for (int i = 0; i + size - 1 < r; i++) {
            for (int j = 0; j + size - 1 < c; j++) {
                for (int p = 0; p < 16; p++) {
                    dp[p][k][i][j] = true;
                    for (int q = 0; q < 4; q++) {
                        int x = i;
                        int y = j;

                        if ((q & 1) == 0) y += size / 2;
                        if (q / 2 == 0) x += size / 2;

                        if (p & 1 << q)
                            dp[p][k][i][j] &= dp[15][k-1][x][y];
                        else
                            dp[p][k][i][j] &= dp[p][k-1][x][y];
                    }
                }
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < 512; i++)
        for (int j = 0; j < 512; j++)
            for (int p = 0; p < 16; p++)
                for (int q = 2; q < 10; q++)
                    ret += dp[p][q][i][j];

    cout << ret << endl;
    
    return 0;
}