ICPC国内予選2016 F問題 : 文字解読

問題. 文字解読

2値画像が2つ与えられる．2つの画像が同じ文字を表しているか判定せよ．画像の白のピクセルは4近傍，黒のピクセルは8近傍で連結しており画像範囲外のピクセルは白とする．画像は各連結成分の包含関係で1つの文字を表す．2つの画像の連結成分の集合をそれぞれ $S, S'$ として，包含関係と色を保つ全単射 $f : S \rightarrow S'$ が存在するとき，2つの画像は同じ文字を表しているとする．

制約： $1 \le$ 画像の高さ・幅 $(H, W) \le 100$

解法. 根付き木の同型性判定

包含関係は遺伝的であり，すべての連結成分は画像範囲外の白のピクセルの集合に含まれるので，画像の連結成分の包含関係は，根を画像範囲外の白ピクセルの集合とする根付き木である．また，包含関係の定義から木の高さの偶奇によって色が異なる．よって，2つの画像が同じ文字を表すかどうかは，構成された根付き木どうしの同型性判定問題に帰着される．
一般グラフの同型性判定問題は，NP完全性の証明も多項式時間のアルゴリズムも見つかっておらず，NP-intermediateではないかと予想されている．ただし，木に制限した同型性判定問題には Aho, HopcroftとUllman による多項式時間アルゴリズム[1] [2] が存在する．
根付き木のアルゴリズムは [3] [4] [5] [6] を参考にした．

計算時間： $O(HW + (HW)^2 \log HW)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

vector<vector<bool>> Input() {
    int h, w;
    cin >> h >> w;
    if (h == 0 && w == 0) return {};

    vector<vector<bool>> image(h + 2, vector<bool>(w + 2, true));
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            char c;
            cin >> c;
            image[i + 1][j + 1] = (c == '.');
        }

    return image;
}

vector<set<int>> Tree(const vector<vector<bool>> &image) {
    const int h = image.size(), w = image.front().size();
    vector<set<int>> tree;
    vector<vector<int>> idx(h, vector<int>(w, -1));

    const int dx[] = {0, -1, 1, 0, -1, 1, -1, 1};
    const int dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            if (idx[y][x] != -1) continue;

            int cur_idx = idx[y][x] = tree.size();
            tree.emplace_back();

            stack<pair<int, int>> st;
            st.push(make_pair(y, x));
            while (!st.empty()) {
                const int cur_y = st.top().first, cur_x = st.top().second;
                st.pop();

                for (int dir = 0; dir < (image[cur_y][cur_x] ? 4 : 8); ++dir) {
                    const int ny = cur_y + dy[dir], nx = cur_x + dx[dir];
                    if (ny < 0 || nx < 0 || h <= ny || w <= nx) continue;

                    if (idx[ny][nx] != -1 && idx[ny][nx] != idx[cur_y][cur_x]) {
                        tree[cur_idx].insert(idx[ny][nx]);
                        tree[idx[ny][nx]].insert(cur_idx);
                    }
                    else if (idx[ny][nx] == -1 && (image[cur_y][cur_x] == image[ny][nx])) {
                        st.push(make_pair(ny, nx));
                        idx[ny][nx] = cur_idx;
                    }
                }
            }
        }
    }

    return tree;
}

string Coding(const int par, const int cur, const vector<set<int>> &tree) {
    vector<string> child;

    for (auto v : tree[cur])
        if (v != par) child.emplace_back(Coding(cur, v, tree));

    sort(child.begin(), child.end());
    string code = "(";
    for (const auto &c : child) code += c;

    return code + ")";
}

inline bool Isomorphism(const vector<set<int>> &t1, const vector<set<int>> &t2) {
    return Coding(-1, 0, t1) == Coding(-1, 0, t2);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    while (true) {
        auto image1(Input());
        if (image1.empty()) break;
        auto image2(Input());

        cout << (Isomorphism(Tree(image1), Tree(image2)) ? "yes" : "no") << '\n';
    }

    return 0;
}