A - Revenge of Voronoi - ボロノイの逆襲

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

「離散ボロノイ図」はボロノイ図の亜種である。 離散ボロノイ図では、図は画素の集合として表現される。 各母点はいくつかの画素の中心に位置しており、 各画素はマンハッタン距離で最も近い母点に所属している。 ここでマンハッタン距離は2つの点 (x_{1}, y_{1})(x_{2}, y_{2}) に対して 以下の式で与えられる距離である。
d = |x_{1} - x_{2}| + |y_{1} - y_{2}|
あなたの仕事は与えられた離散ボロノイ図に対し、 各母点の座標を計算するプログラムを書くことである。 与えられる離散ボロノイ図において、各母点は他の母点と重複しない英小文字で表される。 また各画素は、その点が所属する母点の文字で表される。 一つの画素が複数の母点から等距離にある場合は、 その画素は等距離にある母点のうち、 最も若い英小文字で表される母点に所属する。

入力

入力の1行目には二つの整数、 W (1 ≤ W ≤ 50)H (1 ≤ H ≤ 50) からなり、 それぞれ離散ボロノイ図の幅と高さを表す。 続く H 行には、 W 文字の英小文字が含まれており、 各文字が一つの画素を表す。

出力

サンプル出力に示されている通りに母点の座標を出力せよ。 各行は母点を表す英小文字、X座標、Y座標からなる。 母点はそれぞれを表す英小文字のアルファベット順で出力せよ。 座標は (0,0) を左上の画素の中心とする。 各テストケースにつき、少なくともひとつは解が存在すると仮定して良い。 また、複数の解が存在する場合は、いずれを出力しても構わない。

部分点

  • 1 ≤ W, H ≤ 8 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます
  • 1 ≤ W, H ≤ 16 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます

入力例 1

4 3
ooxx
ooxx
ooxx

出力例 1

o 0 0
x 2 0

入力例 2

4 1
null

出力例 2

l 2 0
n 0 0
u 1 0

入力例 3

4 4
aabb
aabb
ccdd
ccdd

出力例 3

a 0 0
b 2 0
c 0 2
d 2 2

Source Name

ICPC OB/OG会