タイトルがあいまいに思えるので、問題を明確に理解するのに役立つ画像を添付しました。白い領域内の穴を見つける必要があります。穴は、白い領域内の値が「0」の 1 つまたは複数のセルとして定義されます。つまり、値が「1」のセルで完全に囲まれている必要があります (たとえば、ここでは 1、2、3 とマークされた 3 つの穴が表示されます) ）。私は非常に素朴な解決策を思いつきました: 1. マトリックス全体で値 '0' のセルを検索します 2. そのようなセル (黒いセル) が見つかったときに DFS(Flood-Fill) を実行し、タッチできるかどうかを確認しますメインの長方形領域の境界 3. DFS 中に境界に触れることができる場合、それは穴ではなく、境界に到達できない場合は穴と見なされます。
さて、この解決策は機能しますが、この問題に対する他の効率的で高速な解決策があるかどうか疑問に思っていました。
考えを教えてください。ありがとう。
互いにリンクされたセルを格納するある種の「LinkedCells」クラスを作成します。次に、左から右、上から下の順序でセルを 1 つずつチェックし、各セルに対して次のチェックを行います。隣接するセルが黒の場合、このセルをそのセルのグループに追加します。それ以外の場合は、このセルに新しいグループを作成する必要があります。上と左の隣人だけをチェックする必要があります。
UPD: 申し訳ありませんが、グループのマージを忘れていました: 隣接するセルが両方とも黒で、異なるグループに属している場合は、グループを 1 つにマージする必要があります。
エッジに接続されている場合、「LinkedCells」クラスにはフラグが必要です。デフォルトでは false ですが、このグループにエッジ セルを追加すると true に変更できます。2 つのグループをマージする場合は、新しいフラグ||を以前のフラグとして設定する必要があります。最終的に、一連のグループが作成され、false 接続フラグを持つ各グループは「穴」になります。
このアルゴリズムは O(x*y) になります。
個々のセルを頂点とし、隣接する頂点間に発生するエッジを使用して、グリッドをグラフとして表すことができます。次に、幅優先検索または深さ優先検索を使用して、側面の各セルから開始できます。側面に接続されたコンポーネントのみが表示されるため、アクセスされていない黒いセルは穴です。検索アルゴリズムを再度使用して、穴を個別のコンポーネントに分割できます。
編集: 最悪の場合の複雑さは、セルの数に比例する必要があります。そうでない場合は、アルゴリズムに何らかの入力を与え、アルゴリズムが調べていないセルを確認します (サブリニアであるため、未訪問の大きなスポットがあります)。そこに穴。これで、アルゴリズムが穴の 1 つを見つけられない入力が得られました。