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

アルファベット探し

異なる文字が接することは無いので、接しているoを繋げていくと、文字ごとに分けられる。あとは文字ごとにAかBかCかを調べる。最左のピクセルと最右のピクセルの位置から何倍に拡大されているかがわかる。各文字はピクセル数が異なるので、ピクセル数で判別できる。

本番では、中心にピクセルがあればB、中心にピクセルが無くて4隅にピクセルがあればA、そうでなければC、というプログラムを書いたけど、ちょっと面倒。

#include <vector>
#include <string>
#include <iostream>
#include <map>
using namespace std;

//  Union-Find木
class UnionFind
{
    vector<int>p,r;
public:
    UnionFind(int n):p(n,-1),r(n){}
    int find(int x){return p[x]>=0?p[x]=find(p[x]):x;}
    void unite(int x,int y){x=find(x),y=find(y);
        if(x!=y)if(r[x]<r[y])p[x]=y;else p[y]=x,r[x]+=r[x]==r[y];}
    bool same(int x, int y){return find(x)==find(y);}
    bool root(int x){return x==find(x);}
};

int main()
{
    int H,W;cin>>H>>W;
    vector<string> C(H);
    for ( int y=0; y<H; y++ )
        cin>>C[y];
    UnionFind U(H*W);
    for ( int y=0; y<H; y++ )
    for ( int x=0; x<W; x++ )
    {
        if ( x<W-1 && C[y][x]=='o' && C[y][x+1]=='o' )
            U.unite(y*W+x,y*W+(x+1));
        if ( y<H-1 && C[y][x]=='o' && C[y+1][x]=='o' )
            U.unite(y*W+x,(y+1)*W+x);
        if ( x<W-1 && y<H-1 && C[y][x]=='o' && C[y+1][x+1]=='o' )
            U.unite(y*W+x,(y+1)*W+(x+1));
        if ( x<W-1 && y<H-1 && C[y+1][x]=='o' && C[y][x+1]=='o' )
            U.unite((y+1)*W+x,y*W+(x+1));
    }

    map<int,int> Mc;
    map<int,int> Mmin;
    map<int,int> Mmax;

    for ( int y=0; y<H-1; y++ )
    for ( int x=0; x<W-1; x++ )
    if ( C[y][x]=='o' )
    {
        int u = U.find(y*W+x);
        Mc[u]++;
        if ( Mmin.count(u)==0 )
            Mmin[u]=99999999;
        Mmin[u] = min( Mmin[u], x );
        Mmax[u] = max( Mmax[u], x );
    }
    
    int ans[3] = {0};
    for ( map<int,int>::iterator it=Mc.begin(); it!=Mc.end(); it++ )
    {
        int s = (Mmax[it->first]-Mmin[it->first]+1)/5;
        if ( it->second == s*s*12 )
            ans[0]++;
        if ( it->second == s*s*16 )
            ans[1]++;
        if ( it->second == s*s*11 )
            ans[2]++;
    }

    for ( int i=0; i<3; i++ )
        cout << (i>0?" ":"") << ans[i];
    cout << endl;

    return 0;
}