ハニカムつらい

問題概要

下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。

黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。

このような $H \times W$ のマップが与えられたときの、赤太線の長さを求めよ。

制約

$1 \le H, W \le 100$

考えたこと

次のように考えた

建物で覆われているマスはすべて黒色に塗りつぶしてしまう
そうすれば「黒色マスと白色マスとが隣接している箇所」を数えればそれが答えになる

1 の作業については、JOI 公式サイトの解説の図がすべて (引用した)！！

つまり、マップの外側をぐるっと「白色マス」で覆ってしまう。そしてその左上マスから行けるところをすべて求める。これで行けなかったところが「黒く塗りつぶすべきマス」ということになる。

この作業は DFS や BFS でできる。計算量は $O(HW)$ 。

コード

x 座標が横方向、y 座標が縦方向というのは慣れないので、下の実装では逆にした。このとき、ハニカムの移動ベクトルは x 座標の偶奇によって変わるので注意。

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

// x の偶奇による
int dx[2][6] = {
    {1, 0, -1, 0, 1, -1},
    {1, 0, -1, 0, 1, -1}
};
int dy[2][6] = {
    {0, 1, 0, -1, -1, -1},
    {0, 1, 0, -1, 1, 1}
};

int main() {
    int W, H;
    cin >> W >> H;
    vector<vector<int>> fi(H+2, vector<int>(W+2, 0));
    for (int x = 1; x <= H; ++x) for (int y = 1; y <= W; ++y) cin >> fi[x][y];

    vector<vector<bool>> seen(H+2, vector<bool>(W+2, false));
    auto rec = [&](auto self, int x, int y) -> void {
        seen[x][y] = true;
        for (int dir = 0; dir < 6; ++dir) {
            int nx = x + dx[x%2][dir], ny = y + dy[x%2][dir];
            if (nx < 0 || nx >= H+2 || ny < 0 || ny >= W+2) continue;
            if (fi[nx][ny] == 1) continue;
            if (!seen[nx][ny]) self(self, nx, ny);
        }
    };
    rec(rec, 0, 0);
    for (int x = 1; x <= H; ++x) for (int y = 1; y <= W; ++y) if (!seen[x][y]) fi[x][y] = 1;
    int res = 0;
    for (int x = 1; x <= H; ++x) {
        for (int y = 1; y <= W; ++y) {
            if (fi[x][y] == 0) continue;
            for (int dir = 0; dir < 6; ++dir) {
                int nx = x + dx[x%2][dir], ny = y + dy[x%2][dir];
                if (fi[nx][ny] == 0) ++res;
            }
        }
    }
    cout << res << endl;
}