atcoder abc191 C - Digital Graffit

問題

C - Digital Graffiti

解法

H行W列のマス目があり、. は白、# は黒で塗られている。 黒で塗られている部分を多角形として見たとき、何角形になるかを求める問題。

まず問題文が曖昧でサンプルが1ケースしかなく、意図通りに読み取ることが難しかった。

例えばサンプルにはない以下のケース

.....
...#.
..##.
.###.
.....

# を点と考えると3角形にできそうだが、8角形となることを想定した問題だった。一つの # は点ではなく4角形と考える。

上記が読み取れたらあとは各点x,yについて、以下の発想で調べていくと頂点数を求められる。

ある点(x,y) が頂点であることと、その点の周囲4マス (S[x][y], S[x+1][y], S[x][y+1], S[x+1][y+1]) のうち 「#」 がちょうど1個または3個あることが同値

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

int main() {
  int h,w;
  cin >> h >> w;
  char s[h][w];
  REP(i,h) REP(j,w) { cin >> s[i][j]; }

  int ans = 0;
  REP(i,h-1) REP(j,w-1) {
    int cnt = 0;
    // i,jから2x2のグリッドに存在する # の数を数える
    REP(k,2) REP(l,2) {
      if (s[i+k][j+l] == '#') cnt++;
    }
    if (cnt%2) ans++;
  }

  cout << ans << endl;
  return 0;
}

雑感

こういう問題レートが落ちるとどうにも納得いかなくて辛い。