2

文字の行列（A、B、...）があるとします。同じ文字で満たされたすべての連続した「領域」を見つけて、それらの「領域」に対応する頂点を持つグラフを作成したいと思います。対応する領域に共通の境界線がある場合にのみ、グラフの頂点が接続されます。

例えば：

入力行列:
AABC
ABBB
CCDD

エリア:
1(A)、2(B)、3(C)、4(C)、5(D)

出力グラフ (隣接リスト):

1(A)～2(B)、4(C)
2(B) - 1(A)、3(C)、4(C)、5(D)
3(ハ) - 2(ロ)
4(C) - 1(A)、2(B)、5(D)
5(D) - 2(B)、4(C)

私の質問は、マトリックスを指定してそのようなグラフを作成する方法です。

明らかに、次のようにできます。

  • BFS/DFS を実行して、接続されたコンポーネント (「領域」) を見つけます。
  • マトリックスを再度スキャンして、各「領域」の近傍を見つけます。

それを行うためのより簡単で効率的な方法はありますか？

4

1 に答える 1

1

はるかに優れた解決策があるとは思いません。
文字を int に変換すると、ある程度の最適化が可能になります。しかし、これは Big O Notation での努力を変えるものではありません。

速度コンテストに勝つために情報をビット フィールドに保存したい人もいるかもしれませんが、これは努力する価値がなく、コードも読めません。

于 2012-11-30T20:44:32.983 に答える