。ほとんどの石が同じ行または列で除去される-PHPチュートリアル-php.cn

. Most Stones Removed with Same Row or Column

947。ほとんどの石が同じ行または列で削除されました

難易度:中

トピック:ハッシュテーブル、深さ優先検索、ユニオン検索、グラフ

2D 平面上で、いくつかの整数座標点に n 個の石を配置します。各座標点には最大 1 つの石を含めることができます。

石は、削除されていない別の石と同じ行または同じ列を共有している場合、削除できます。

長さ n の石の配列が与えられ、stones[i] = [xi, yi] が i^番目の石の位置を表す場合、削除できる石の最大数を返します。.

例 1:

入力:石 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
出力:5
説明:5 つの石を削除する 1 つの方法は次のとおりです。
1. 石 [2,2] は [2,1] と同じ行を共有しているため、削除します。
2. 石 [2,1] は [0,1] と同じ列を共有しているため、削除します。
3. 石 [1,2] は [1,0] と同じ行を共有しているため、削除します。
4. 石 [1,0] は [0,0] と同じ列を共有しているため、削除します。
5. 石 [0,1] は [0,0] と同じ行を共有しているため、削除します。
6. 石 [0,0] は、まだ平面上にある別の石と行/列を共有していないため、削除できません。

例 2:

入力:石 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
出力:3
説明:3 つの移動を行う 1 つの方法は次のとおりです。
1. 石 [2,2] は [2,0] と同じ行を共有しているため、削除します。
2. 石 [2,0] は [0,0] と同じ列を共有しているため、削除します。
3. 石 [0,2] は [0,0] と同じ行を共有しているため、削除します。
4. 石 [0,0] と [1,1] は、まだ平面上にある別の石と行/列を共有していないため、削除できません。

例 3:

入力:石 = [[0,0]]
出力:0
説明:[0,0] は平面上の唯一の石なので、削除できません。

制約:

1
0 i、y_i4
同じ座標点に 2 つの石はありません。

解決策:

深さ優先検索 (DFS) アプローチを使用してソリューションを実装できます。このアイデアは、行または列によって接続されている石を、同じ接続されたコンポーネントの一部として考えることです。すべての接続コンポーネントを見つけたら、削除できる石の最大数は、石の合計数から接続コンポーネントの数を引いたものになります。

このソリューションを PHP で実装してみましょう:947。同じ行または列で削除されたほとんどの石

リーリー

説明：

DFS 関数:
- dfs 関数は、同じ接続コンポーネント内にあるすべての石を探索するために使用されます。ストーンが現在のストーンに (同じ行または列内で) 接続されている場合、そのストーンに対して DFS を再帰的に実行します。
メイン関数:
- すべての石を反復処理し、まだ訪問されていない石ごとに DFS を実行して、同じ接続コンポーネント内のすべての石をマークします。
- 接続されたコンポーネントの数を数えます。その結果は、石の合計数から接続されたコンポーネントの数を引いたものになります ($n - $numComponents)。
実行例:
- 最初の例では、5 つの石を削除できることが正しく検出され、1 つの石は削除できないことがわかります。