次の配列には連結集合がいくつありますか?
1 0 0 1
0 0 1 0
0 0 1 0
1 0 0 1
「接続されたセット」は、1 が言及され、そのセット内に隣接関係を共有する他のセルが少なくとも 1 つあるセルのグループとして定義できます。1 を含むセルと、1 を含む周囲の隣接セルがないセルは、1 つのセルを含むセットと見なすことができます。ネイバーは、特定のセルに隣接する 8 つの方向 (つまり、 N 、 W 、 E 、 S 、 NE 、 NW 、 SE 、 SW 方向 ) のすべてのセルとして定義できます。セルはそれ自体の隣人ではありません。
実際、私はこれに固執しており、この質問の接続セットの定義が何を意味するのか理解できません
セットを強調した画像は次のとおりです。
ルールは次のように適用されます（私が理解している限り）：
OPには「「接続されたセット」は、1つが言及され、そのセットに少なくとも1つの他のセルがあるセルのグループとして定義できる」と書かれているため、3番目のポイントはよくわかりませんが、その後また、「セルに 1 があり、周囲に 1 がないセルは、セルが 1 つのセットと見なすことができる」とも述べているため、非常にあいまいです。
単一セルがセットではなく、カウントがそれぞれ 1 と 5 である場合。
問題を解決する 1 つのアプローチは、フラッド フィル アルゴリズムを使用することです。
1をチェックして0にし、すべての方向をチェックして、1が含まれている場合は0にします（すべての方向に再帰呼び出しを行うだけです）
アレイ全体のチェックが完了した後、何回直面したか 1 が答えです
たとえば、
1 0 0 1
1 0 0 1
1 0 0 1
1 0 1 0
00 の要素は 1 になり、0 になり、すべての方向でチェックします。10 の位置に 1 があるため、0 にします。もう一度チェックすると、20 と 30 の位置が得られるため、1 としてカウントされます。
次に03に移動して0にし、1をチェックします。したがって、1を含むセルは13です。ゼロにして、23に移動し、最後に32に移動し、カウンターをインクリメントするため、2になります
他のセルに1が含まれていないため、すべてのセルをチェックします。したがって、接続されたセットの合計は2です