F: 文字解読
問題
グリッドの2値画像が与えられる。この画像は「文字」として認識することができる。
- 白マスは4方向に連結する
- 黒マスは8方向に連結する
- 画像の外側は無限に白マスとし、背景と呼ぶ
また、白マスや黒マスの連結成分について包含の条件がある(省略)。
包含関係を連結成分同士の二項関係とすると、その二項関係を「文字」の定義とする。
2つの画像が与えられたとき、その画像が同じ「文字」かどうか判定せよ。
同じ「文字」であるとは、二項関係が保存される連結成分の全単射が存在することである。
解法
包含関係の定義がややこしいが、包含関係は輪になって一周することはない。
つまり、連結成分を頂点とし、隣り合う連結成分の間に辺を張ると、包含関係を気にすることなく、自然とグラフは「背景を根とする木構造」を得ることができる。
頂点はその祖先に包含されていると言える。
2つ根付き木は、根は固定で対応し、残りの頂点はラベルを無視して、同じ木構造であるならば画像は同じ「文字」である。根付き木の同型性判定問題である。
木の同型性判定は、「同型の木ならばいつも同じ値」になるハッシュ関数を求めることで達成できる。
子ノードのハッシュ値をコンマ区切りで並べたものを文字列とし、その文字列のハッシュ値をノードのハッシュ値とする。
hash(treeの頂点v): if vが葉: return 0 else: vの子をc_1, ..., c_dとする hash(c_i)を再帰的に求める hash(c_1), ..., hash(c_d) をソートしたものをh_1, ..., h_dとする return str_hash(h_1,h_2,...,h_d)
ソートをすることで子の順番を無視することができる。
str_hashが衝突しなければ問題ない。
簡単な衝突の回避として、map < string, int >で初めて見たら新しい値をハッシュ値とし、見たことある文字列なら同じ値を返せばよい。
コード
#include<stack> #include<map> #include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } typedef int Hash; map<string, Hash> mp; char buf[999]; char *end; Hash rooted_tree_hash(VI G[]) { VI ord; ord.push_back(0); for (int i=0; i<(int)ord.size(); i++) { int v = ord[i]; EACH (e, G[v]) ord.push_back(*e); } vector<Hash> h(ord.size()); REP (i_, ord.size()) { int v = ord[(int)ord.size() - i_ - 1]; vector<Hash> sub; EACH (e, G[v]) sub.push_back(h[*e]); sort(sub.begin(), sub.end()); end = buf; EACH (e, sub) { end += sprintf(end, "%d", *e); end += sprintf(end, ";"); } *end = 0; string key = buf; if ((int)mp.count(key) == 0) mp.insert(make_pair(key, (Hash)mp.size())); h[v] = mp[key]; } return h[0]; } const int dy[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; const int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 }; int H, W; VI G[10111]; bool in(int y, int x) { return 0 <= y && y < H && 0 <= x && x < W; } char S[111][111]; int F[111][111]; Hash read_image() { scanf("%d%d", &H, &W); if (H == 0 && W == 0) return -1; memset(S, '.', sizeof S); REP (i, H) { scanf("%s", S[i+1]+1); S[i+1][W+1] = '.'; } H += 2; W += 2; int cnt = 0; memset(F, -1, sizeof F); REP (i, H) REP (j, W) if (F[i][j] == -1) { stack<int> Y, X; Y.push(i); X.push(j); F[i][j] = cnt; int D = (S[i][j] == '.'? 4: 8); while (!Y.empty()) { int y = Y.top(); Y.pop(); int x = X.top(); X.pop(); REP (d, D) { int yy = y + dy[d]; int xx = x + dx[d]; if (in(yy, xx) && S[y][x] == S[yy][xx] && F[yy][xx] == -1) { F[yy][xx] = cnt; Y.push(yy); X.push(xx); } } } cnt++; } vector<pair<int, int> > E; REP (i, H-1) REP (j, W-1) { int mi, ma; mi = min(F[i][j], F[i+1][j]); ma = max(F[i][j], F[i+1][j]); if (mi != ma) E.push_back(make_pair(mi, ma)); mi = min(F[i][j], F[i][j+1]); ma = max(F[i][j], F[i][j+1]); if (mi != ma) E.push_back(make_pair(mi, ma)); } sort(E.begin(), E.end()); E.erase(unique(E.begin(), E.end()), E.end()); REP (i, cnt) G[i].clear(); EACH (e, E) G[e->first].push_back(e->second); return rooted_tree_hash(G); } int main() { while (1) { Hash a = read_image(); if (a == -1) break; Hash b = read_image(); puts(a == b? "yes": "no"); } return 0; }
日記
木の同型性判定またでたのか
