Submission #1390140

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
// #include <unordered_map>
#include <set>
#include <utility>
#include <bitset>
#include <limits>
#include <climits>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define ALL(c)  (c).begin(),(c).end()


class UnionFind {
 public:
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    assert(0 <= x && x < data.size());
    assert(0 <= y && y < data.size());
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};


vector<int> solve(vvi& mp) {
    int R=mp.size()-2, C=mp[0].size()-2;
    UnionFind uf(R*C);

    rep(r,R) rep(c,C) {
        // printf("%d %d\n", r,c);
        if (!mp[1+r][1+c]) continue;

        if (mp[1+r-1][1+c-1]) uf.unionSet(r*C+c, (r-1)*C+(c-1));
        if (mp[1+r-1][1+c  ]) uf.unionSet(r*C+c, (r-1)*C+c);
        if (mp[1+r-1][1+c+1]) uf.unionSet(r*C+c, (r-1)*C+(c+1));
        if (mp[1+r  ][1+c-1]) uf.unionSet(r*C+c, r*C+(c-1));
        //
        if (mp[1+r  ][1+c+1]) uf.unionSet(r*C+c, r*C+(c+1));
        if (mp[1+r+1][1+c-1]) uf.unionSet(r*C+c, (r+1)*C+(c-1));
        if (mp[1+r+1][1+c  ]) uf.unionSet(r*C+c, (r+1)*C+c);
        if (mp[1+r+1][1+c+1]) uf.unionSet(r*C+c, (r+1)*C+(c+1));
    }

    vector<int> rmin(R*C, 1001), rmax(R*C, -1), cmin(R*C, 1001), cmax(R*C, -1);
    rep(r,R) rep(c,C) {
//        if (!mp[1+r][1+c]) continue;
        int root = uf.root(r*C+c);
        // if (uf.size(r*C+c))
        rmin[root] = min(rmin[root], r);
        rmax[root] = max(rmax[root], r);
        cmin[root] = min(cmin[root], c);
        cmax[root] = max(cmax[root], c);
    }

    // vector<int> w(R*C), h(R*C);
    int na=0, nb=0, nc=0;
    rep(i, R*C) {
        int area = -uf.data[i];
        if (area <= 1) continue;

        int w = cmax[i] - cmin[i] + 1;
        int h = rmax[i] - rmin[i] + 1;
        assert(w == h);
        int mag = w / 5;
        // printf("(i=%d) area=%d w=%d h=%d mag=%d\n", i,area,w,h,mag);
        assert(area % (mag*mag) == 0);
        area /= (mag*mag);
        switch (area) {
            case 12: ++na; break;
            case 16: ++nb; break;
            case 11: ++nc; break;
        }
    }

    return vector<int>{ na, nb, nc };
}

int main(){
    int R, C; cin >> R >> C;
    vvi mp(R+2, vi(C+2, 0));
    rep(r,R) {
        string s; cin>>s;
        // assert(s.size() == W);
        rep(c,C) {
            mp[1+r][1+c] = (s[c]=='o') ? 1 : 0;
        }
    }

    vector<int> res = solve(mp);
    printf("%d %d %d\n", res[0], res[1], res[2]);
    return 0;
}

Submission Info

Judge Result