Atcoder ARC #006 D. アルファベット探し

Atcoder ARC #006 D. アルファベット探し

D: アルファベット探し - AtCoder Regular Contest 006 | AtCoder

ある決められた図形A, B, Cの非負整数倍拡大図形が90度毎の回転を許していくつか描かれているので、A, B, Cがそれぞれ何個ずつ含まれているかを数える問題。仮に、拡大されたものが現れないとするならば、それぞれの図形が含むマスの数をカウントするだけで、どの図形だったのかは判断できそうである（それぞれA=12, B=16, C=11なので）。どれも少なくとも８方向のいずれかで繋がっているので、これは典型的な幅優先探索で書ける。さて、実際には拡大されたものがあって、例えばAの4倍拡大とBの3倍拡大のいずれもが48個とカウントされてしまって区別できなくなってしまう。そこで、倍率を計算しておくことにする。左上から右に探索をしているので、一番最初に見つかったマスは、拡大された「１つの点」の左上に位置している。よって、ratio = 1から正方形の探索をしてみて、すべて'o'マスならratioを増やしてさらに探索をするということを繰り返せば、その正方形が構成できなくなったときのratioが倍率とわかる（めんどくさいのでふつうに実装した）。そして最後にカウントをratio * ratioで割れば、結局12, 16, 11のいずれかになるはずなので、これで判定可能になる。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)

static const int dx[] = { 1, -1, 0, }, dy[] = { 0, 1, -1 }; //8方向の探索用

signed main() { 
        int H, W;
        cin >> H >> W;
        vector<string> c(H);
        rep(i, H) cin >> c[i];
        bool used[1010][1010] = { 0 };
        int ansA = 0, ansB = 0, ansC = 0;
        rep(i, H) rep(j, W) {
                if (used[i][j]) continue;
                used[i][j] = true;
                if (c[i][j] == '.') continue;
                int ratio = 1;
                bool f = true;
                while (f) {
                        rep(y, ratio) rep(x, ratio) if (c[i + y][j + x] == '.') f = false; //c[i][j]からみてy, xだけ探索してチェック
                        if (f) ratio ++;
                }
                ratio --;
                int cnt = 0;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                        pair<int, int> s = q.front(); q.pop();
                        cnt ++;
                        int y = s.first;
                        int x = s.second;
                        rep(ddx, 3) rep(ddy, 3) { //8方向すべて探索
                                int ny = y + dy[ddy];
                                int nx = x + dy[ddx];
                                if (!used[ny][nx] && c[ny][nx] =='o') {
                                        used[ny][nx] = true;
                                        q.push(make_pair(ny, nx));
                                }
                        }
                }
                int detect = cnt / (ratio * ratio);
                if (detect == 12) ansA ++;
                if (detect == 16) ansB ++;
                if (detect == 11) ansC ++;
        }
        cout << ansA << ' ' <<  ansB << ' ' << ansC << endl;
        return 0;
}               

余計な図形が入っていないことが保証されていたので易しかった。

追記：他の方のコードを見てみると、yminとymaxを保持するやり方を見つけた。これで倍率が一意に定まる程度に大体の大きさがわかるというわけだって。よく考えたらそりゃそうだった。