読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, F 解答

F: 文字解読

問題

グリッドの2値画像が与えられる。この画像は「文字」として認識することができる。

  1. 白マスは4方向に連結する
  2. 黒マスは8方向に連結する
  3. 画像の外側は無限に白マスとし、背景と呼ぶ

また、白マスや黒マスの連結成分について包含の条件がある(省略)。
包含関係を連結成分同士の二項関係とすると、その二項関係を「文字」の定義とする。

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;
}

日記

木の同型性判定またでたのか