algorithm - 二重正方形の最大パッキングのためのグラフ アルゴリズム

Question

接続された正方形の領域 (左側の画像) があり、その領域に収まる「二重」正方形の最大数を見つけたい (右側の画像)。

私のアプローチは、元の領域をグラフとして表すことです。ここで、各正方形は、下、上、左、および/または右の正方形にエッジで接続された頂点を表します。

BFS アルゴリズムを使用して、各頂点を調べて色を適用することで実現できると考えていました。しかし、動的計画法でそれを行うこともできると感じています...途中で助けが必要です!

Answer 1

補題 1:

正方形をグラフの頂点と見なすと、その特殊な構造により、グラフは二部グラフになります。各頂点から隣接するすべての頂点にエッジをリンクします。

証拠：

各正方形を白または黒でペイントすると、隣接する 2 つの黒も 2 つの白も隣接しないように形成できるため、グラフのエッジは 1 つの黒と 1 つの白の間のみになります。

アルゴリズム：

二部グラフを構築した後、二部グラフの最大一致を見つけることができ、最大一致の値が答えになります。ハンガリアン アルゴリズムまたはより高速な Hopcroft-Karp アルゴリズムを使用して、答えを計算できます。