0

「ブロック」のグリッド(2D配列の形式で、5 * 5、17 * 17など)があり、ブロックを自由に追加または削除できますが、中央にあるブロックは常に残す必要がありますそこの。

ローカル ネイバーがある場合、ブロックを配置できます: 右/左/上/下 (少なくとも 1 つ)。

いくつかのブロックを削除すると、他のブロックが中央ブロックへの「接続」なしで分離されたままになる可能性があり、これを回避したいと考えています。

すべてのブロックが中心に接続されているかどうかを確認するための簡単な解決策を探しています。データであり、それほど頻繁ではありません)。最初に頭に浮かんだのは、これをパス検索として実装することでしたが、それはやり過ぎのようです。

私はC++を使用していますが、違いはありません。

4

1 に答える 1

1

DFS/BFS を使用して連結成分を見つける必要があります。初期グラフを作成し、新しいブロックを追加するときに新しいエッジを追加したり、ブロックを削除するときにエッジを削除したりできます。ブロックを削除するときは、それらのエッジを一時的に削除しますこれは単純で、DFS を再度実行します。切断されない場合は、そのブロックを削除できます。

DFS を実装するのは約 8 行だけであり、小さなデータ セットの場合、これは洗練されています。

于 2013-07-03T12:20:24.837 に答える