AOJ 1613 Deciphering Characters

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp

解法

包含関係は，一番背景連結成分を根とした木構造になっていることがわかる．
よって，背景連結成分を根として，各再帰段階でBFSをするDFSを行えば，その木構造が得られる．
あとは，木が同一のものであるかを判定する必要があるが，これは木を文字列によって表現することで実現ができる（ノードの数はそんなに多くないはずなので）．
各ノードの部分木を表す文字列が得られれば，それをソートして結合し，括弧でくくったものを返せば，木の一意的な表現が得られる．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
 
constexpr int dx[2][8] = {{0, 1, 0, -1, 0, 0, 0, 0}, {0, 1, 1, 1, 0, -1, -1, -1}};
constexpr int dy[2][8] = {{1, 0, -1, 0, 0, 0, 0, 0}, {-1, -1, 0, 1, 1, 1, 0, -1}};
 
string dfs(int y, int x, vector<vector<bool>>& visited, vector<string> const& v) {
    const int H = v.size();
    const int W = v[0].size();
    bool black = v[y][x] == '#';
    visited[y][x] = true;
    queue<pii> que;
    que.push(make_pair(y, x));
    vector<pii> next;
    while(!que.empty()) {
        auto p = que.front();
        int y2 = p.first,
            x2 = p.second;
        que.pop();
        for(int i = 0; i < (black ? 8 : 4); ++i) {
            int ny = y2 + dy[black][i],
                nx = x2 + dx[black][i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || visited[ny][nx]) {
                continue;
            }
            if(v[ny][nx] != v[y][x]) {
                next.push_back(make_pair(ny, nx));
            } else {
                visited[ny][nx] = true;
                que.push(make_pair(ny, nx));
            }
        }
    }
 
    string res = "(";
    vector<string> tmp;
    for(auto& to : next) {
        if(visited[to.first][to.second]) {
            continue;
        }
        tmp.push_back(dfs(to.first, to.second, visited, v));
    }
    sort(tmp.begin(), tmp.end());
    for(auto& s : tmp) {
        res += move(s);
    }
    res += ")";
    return res;
}
 
int main() {
    int h1, w1;
    while(cin >> h1 >> w1, h1) {
        vector<string> v(h1 + 2, string(w1 + 2, '.'));
        vector<vector<bool>> visited1(h1 + 2, vector<bool>(w1 + 2));
        for(int i = 1; i <= h1; ++i) {
            string s;
            cin >> s;
            v[i] = "." + s + ".";
        }
        int h2, w2;
        cin >> h2 >> w2;
        vector<string> v2(h2 + 2, string(w2 + 2, '.'));
        vector<vector<bool>> visited2(h2 + 2, vector<bool>(w2 + 2));
        for(int i = 1; i <= h2; ++i) {
            string s;
            cin >> s;
            v2[i] = "." + s + ".";
        }
        bool same = dfs(0, 0, visited1, v) == dfs(0, 0, visited2, v2);
        cout << (same ? "yes" : "no") << endl;
    }
}