Fissure Puzzle Easy [ACPC2017 Day2 D]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=D

解説

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2538242&cid=ACPC2017Day2

貪欲に解く。
「f(int sx, int sy, int tx, int ty) := (sx,sy)から(tx, ty)の四角形の中の座標のうちいずれかを選んで、最終型にするために必要な回数を返す」を作り、再帰的に処理していく。
そのマスを選んで分割できるかは、そのマスの上下左右が'x'であるかを見れば良いが、これは二次元累積和を使えばできる。
四角形の中に'x'が無ければ、そこでうちやめ。

template<int VW, int VH> struct Ruisekiwa2D {
    int v[VH][VW];
    void set(int x, int y, int c) { v[y][x] = c; }
    void build() {
        rep(y, 0, VH) rep(x, 0, VW) {
            if (0 < y) v[y][x] += v[y - 1][x];
            if (0 < x) v[y][x] += v[y][x - 1];
            if (0 < y && 0 < x) v[y][x] -= v[y - 1][x - 1];
        }
    }
    int get(int sx, int sy, int tx, int ty) {
        assert(sx <= tx && sy <= ty);
        int rs = v[ty][tx];
        if (0 < sx) rs -= v[ty][sx - 1];
        if (0 < sy) rs -= v[sy - 1][tx];
        if (0 < sx && 0 < sy) rs += v[sy - 1][sx - 1];
        return rs;
    }
};





int N;
string A[201];
Ruisekiwa2D<201, 201> rui;
//--------------------------------------------------------------------------------------------------
int f(int sx, int sy, int tx, int ty) {
    if (rui.get(sx, sy, tx, ty) == 0) return 0;
 
    rep(y, sy, ty + 1) rep(x, sx, tx + 1) if(y % 2 == 1) if(x % 2 == 1) {
        if (rui.get(x, sy, x, ty) == (ty - sy + 1)) if (rui.get(sx, y, tx, y) == (tx - sx + 1)) {
            int A = f(sx, sy, x - 1, y - 1);
            if (A < 0) continue;
            int B = f(x + 1, sy, tx, y - 1);
            if (B < 0) continue;
            int C = f(sx, y + 1, x - 1, ty);
            if (C < 0) continue;
            int D = f(x + 1, y + 1, tx, ty);
            if (D < 0) continue;
 
            return A + B + C + D + 1;
        }
    }
 
    return -1;
}
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(y, 0, N) rep(x, 0, N) if(A[y][x] == 'x') rui.set(x, y, 1);
    rui.build();
 
    cout << f(0, 0, N - 1, N - 1) << endl;
}