行列内の接続された空でないセルの数を更新するクエリ

行列は、行と列で編成されたセルのコレクションと考えることができます。各セルには、空または空でない値を含めることができます。コンピューター プログラミングでは、データを 2 次元グリッドで表すために行列がよく使用されます。

この記事では、行列の更新の可能性を考慮して、行列内の接続された空でないセルの数を効率的にカウントする方法について説明します。この問題を解決するさまざまな方法を検討し、実装を示す実際のコード例を提供します。

行列内の接続された空でないセルの数をクエリし、C/C を使用してそれを更新するための基本的な構文は、次のように定義できます -

ここで、matrix は入力「matrix」、「rows」と「cols」はそれぞれ行列の行数と列数を表します。関数「queryCount」は、行列内の接続された空でないセルの数を表す整数値を返します。

この問題を解決するには、次のアルゴリズムに従うことができます -

- 変数「count」を 0 に初期化します。これにより、接続された空でないセルの数が保存されます。

ステップ 2 - 行列内の各セルを繰り返します。

ステップ 3 - 各セルについて、空ではないか (つまり、null 以外の値が含まれているか) どうかを確認します。

ステップ 4 - セルが空でない場合は、[カウント]を 1 つ増やします。

ステップ 5 - セルに空ではない隣接セルがあるかどうかを確認します。

ステップ 6 - 隣接するセルが空でない場合は、カウントを 1 増やします。

ステップ 7 - 隣接するすべてのセルに対してステップ 5 ～ 6 を繰り返します。

ステップ 8 - 8: 行列内のすべてのセルを反復処理した後、最終結果として「count」を返します。

- この問題を解決する一般的な方法は、深さ優先検索 (DFS) アルゴリズムを使用することです

• 方法 2 - 更新された行列内の結合を持つ空でないセルの数を見つけるクエリを実装する別の方法は、幅優先検索 (BFS) アルゴリズムを使用することです。 。

• 方法1 このアプローチでは、DFS アルゴリズムは行列を再帰的に走査し、訪問したセルを追跡して二重カウントを回避します。

例 1

このメソッドは、2 次元行列に対して深さ優先検索を実行します。マトリックスの次元、セル値、クエリ数はランダムに決定されます。 countConnectedCells サブルーチンは DFS を実行し、指定された行と列のセルから始まる、接続された空でないセルの数を返します。 updateCell 関数は、行列内のセルの値を更新します。 main 関数は、現在の時刻を使用してランダム シードを開始し、次にランダムな行列サイズと要素を生成し、その後にランダムな数のクエリを生成します。各クエリに対して、コードはカウント クエリ (1) または更新クエリ (2) をランダムに選択し、適切なアクションを実行します。クエリのタイプが 1 の場合、countConnectedCells 関数が呼び出されて、接続されている空でないセルの数が決定され、結果が出力されます。クエリ タイプが 2 の場合、updateCell 関数を呼び出して、指定されたセルの値を調整します。

方法 2

このアプローチでは、幅優先検索 (BFS) は、行列内の接続された空でないセルの数を見つけるために使用できる別のグラフ走査アルゴリズムです。 BFS では、特定のセルから開始して、そのセルに隣接するすべてのセルを幅優先方式 (つまり、レイヤーごと) で探索します。キューを使用してどのセルがアクセスされているかを追跡し、複数のカウントを避けるためにアクセスされたセルにマークを付けます。

例 2

このコードは、2次元行列に対して幅優先探索アルゴリズムを実行するソフトウェアを構成します。行列の次元、セル値、クエリの数は任意に生成されます。コードには 2 つのサブルーチンが含まれています。1 つは BFS を実行するもので、もう 1 つは行列内のセルを調整するものです。

BFS 操作は、ランダムに選択されたセルから開始され、隣接するセルをチェックして、それらが相互接続されているか、占有されていないかを判断します。存在する場合、それらはキューに追加され、同様の方法で処理されます。行列内のセルを更新するには、その値を変更するだけです。マトリックスとクエリ番号を生成した後、コードは BFS クエリまたは更新クエリをランダムに選択し、適切な操作を実行します。 BFS クエリの結果は、選択されたセルから始まる相互接続された空きセルの数です。

この記事では、C/C を使用して行列内の接続された空でないセルの数を見つけて更新する 2 つの方法について説明しました。深さ優先検索 (DFS) アルゴリズムと和集合検索 (素集合の和集合)。特定の使用例に最も適切な方法を選択する前に、各方法の時間計算量と空間計算量を分析することが重要です。

以上が行列内の接続された空でないセルの数を更新するクエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。