c++ - 与えられた MxN ボードで 2 種類の文字のみからなる最大の長方形領域を見つけます

Question

重複の可能性:最大部分行列アルゴリズムを見つける

---

問題について助けが必要です。

各行に文字 (az) で表されるMxNボードがある場合、2 種類の文字しかない最大の領域を見つける必要があります。領域は長方形でなければなりません。例を次に示します。MN

4x4:

AAAA
ABBC
BBCA
DCAA

出力は 6 になります。文字が 2 種類しかない最大の長方形の領域は上隅 AAA-ABB にあるため、A と B (2 種類) しかありません。

Answer 1

いくつかのアイデア:

1. 徹底的に調べる必要があると思います。ただし、基準に適合する領域 A の長方形を見つけたら、A より小さい領域の長方形を調べる必要はありません。

2. サイズが 2x2 または 1x3 で、少なくとも 3 つの異なる文字を含む四角形は、ソリューションの一部にすることはできません。おそらく、それらの領域を最初に「タグ付け」してから、それらのタグ付けされた領域を含まない長方形のみを考慮して、入力を 2 回スキャンすることができます。

3. 基準 (つまり、すべてのセル) に適合する 1x1 の四角形を見つけます。この四角形を一方向または他方向に拡張しても基準に適合するかどうかを確認します。どちらの方向にも拡張できなくなり、基準に適合するまで続行します。長方形をどちらの方向にも拡張できる場合があります。これらのケースを確認するには、バックトラックする必要があります (この例では、左上の 2x2 はどちらの方向にも拡張できます)。これは私には検索の問題のように思えます - いくつかの検索テクニックを読んでください。

Answer 2

完全な実用的な解決策ではありませんが、この問題を解決するための可能な方向性:

接続された領域でボードを表現してみてください。各領域は、同じ文字を含む 1 つ以上の接続された場所を表します。次に、領域を結合してみます。