[AtCoder] ABC 191 C – Digital Graffiti

問題

方針

多角形の辺と接する白マスの集合を考えます。このの白マスは複数の辺と接していることもあります。また、辺は縦か横の辺の \( 2 \) 通りです。

横の辺の本数

横の辺は、多角形の辺と接する白マスから構成されていることを考えると、上に白マス、下に黒マスまたは、上に黒マス、下に白マスというパターンがあります。

上に白マス、下に黒マスのパターンの辺の白マスは連続してこの状態であることを利用して辺の数を数えます。同様にして、上に黒マス、下に白マスというパターンについても求めます。

縦の辺の本数

横の辺のときと同様に、縦の辺は、左に白マス、右に黒マスまたは、左に黒マス、右に白マスというパターンがあります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int H, W;
    cin >> H >> W;
    string S[H];
    for (int i = 0; i < H; i++) {
        cin >> S[i];
    }
    int ans = 0;
    bool vis[H][W] = {};
    for (int i = 0; i + 1 < H; i++) {
        for (int j = 0; j < W; j++) {
            if (vis[i][j]) continue;
            if (S[i][j] == '#') continue;
            if (S[i + 1][j] == '.') continue;
            ans++;
            vis[i][j] = true;
            for (int k = j + 1; k < W; k++) {
                if (S[i][k] == '#' || S[i + 1][k] == '.') break;
                vis[i][k] = true;
            }
        }
    }
    fill(vis[0], vis[H], false);
    for (int i = 1; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (vis[i][j]) continue;
            if (S[i][j] == '#') continue;
            if (S[i - 1][j] == '.') continue;
            ans++;
            vis[i][j] = true;
            for (int k = j + 1; k < W; k++) {
                if (S[i][k] == '#' || S[i - 1][k] == '.') break;
                vis[i][k] = true;
            }
        }
    }
    fill(vis[0], vis[H], false);
    for (int i = 1; i < W; i++) {
        for (int j = 0; j < H; j++) {
            if (vis[j][i]) continue;
            if (S[j][i] == '#') continue;
            if (S[j][i - 1] == '.') continue;
            ans++;
            vis[j][i] = true;
            for (int k = j + 1; k < H; k++) {
                if (S[k][i] == '#' || S[k][i - 1] == '.') break;
                vis[k][i] = true;
            }
        }
    }
    fill(vis[0], vis[H], false);
    for (int i = 0; i + 1 < W; i++) {
        for (int j = 0; j < H; j++) {
            if (vis[j][i]) continue;
            if (S[j][i] == '#') continue;
            if (S[j][i + 1] == '.') continue;
            ans++;
            vis[j][i] = true;
            for (int k = j + 1; k < H; k++) {
                if (S[k][i] == '#' || S[k][i + 1] == '.') break;
                vis[k][i] = true;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}