グリッド内の保護されていないセルを数える

2257。グリッド内の保護されていないセルを数える

難易度: 中

トピック: 配列、行列、シミュレーション

0 インデックス付き m x n グリッドを表す 2 つの整数 m と n が与えられます。また、2 つの 2D 整数配列のガードとウォールも与えられます。ここで、guards[i] = [row_i、col_i]、walls[j] = [row_j、col_j] は i ^番目 ガードの位置を表し、それぞれ j ^番目 の壁。

警備員は、壁や他の警備員によって妨げられない限り、自分の位置から開始して 4 つの基本方向 (北、東、南、または西) のすべてのセルを見ることができます。セルを確認できる少なくとものガードがいる場合、セルはガードされています。

保護されていないの空きセルの数を返します。

例 1:

• 入力: m = 4、n = 6、ガード = [[0,0],[1,1],[2,3]]、壁 = [[0,1],[2, 2]、[1,4]]
• 出力: 7
• 説明: 上の図では、ガードされたセルとガードされていないセルがそれぞれ赤と緑で示されています。
  • ガードされていないセルは合計 7 つあるため、7 を返します。

例 2:

• 入力: m = 3、n = 3、ガード = [[1,1]]、壁 = [[0,1],[1,0],[2,1],[1, 2]]
• 出力: 4
• 説明: 保護されていないセルは、上の図では緑色で示されています。
  • ガードされていないセルは合計 4 つあるため、4 つを返します。

制約:

• 1 5
• 2 5
• 1 4
• 2
• ガード[i].length == 壁[j].length == 2
• 0 i, 行_j <うーん
• 0 _=coli_,colj
< n
• ガードと壁のすべての位置はユニーク
です。

ヒント:

グリッドを表す 2D 配列を作成します。ガードから見えるタイルにマークを付けていただけますか?
ガードを繰り返し、4 つの方向ごとに現在のタイルを進め、タイルをマークします。いつ前進をやめるべきですか?

解決策:

少なくとも 1 つのガードによって守られているセルをマークする必要があります。警備員は基本的な 4 方向 (北、南、東、西) を見ることができますが、その視界は壁によって遮られています。このプロセスをシミュレートし、保護されていないセルの数を数えることができます。

アプローチ：

1. グリッドの作成: グリッドを 2D 配列として表すことができ、各セルは壁、ガード、または空のいずれかになります。
2. ガードされたセルをマークする: 各ガードについて、4 方向 (北、南、東、西) に繰り返し、見えるすべてのセルをマークし、壁または別のガードに遭遇したときに停止します。
3. ガードされていないセルを数える: ガードされたセルをマークした後、ガードされておらず壁でもないセルの数を数えます。

手順:

1. グリッドの初期化: グリッドを表す 2D 配列を作成します。繰り返しながら、セルに壁、ガード、ガードされたエリアをマークします。

2. ガード カバレッジのシミュレーション:

   • 衛兵は 4 方向 (北、南、東、西) を見ることができます。
   • 壁または別の警備員に遭遇するまで、各警備員が警備しているセルにマークを付けます。

3. ガードされていないセルのカウント: すべてのガードを処理した後、壁、ガード、ガードされていないセルをカウントします。

このソリューションを PHP で実装してみましょう: 2257。グリッド内の保護されていないセルを数える

説明：

1. 初期化:

   • グリッドは空のセルの場合は 0 で初期化されます。壁とガードには固有の定数がマークされています。

2. ガードシミュレーション:

   • 各ガードについて、4 方向すべての動きをシミュレートし、壁または別のガードにぶつかるまでセルをガード済みとしてマークします。

3. 保護されていないセルの数:

   • すべてのガードを処理した後、グリッドを反復処理し、まだ 0 としてマークされているセルをカウントします。

パフォーマンス：

• 時間計算量: O(m x n g x d)、g はガードの数、d は、各ガードが移動できる方向のセルの数です。旅行。
• 空間の複雑さ: グリッドの場合は O(m x n)。

時間計算量:

• グリッドの初期化: _O(m * n)、ここで _m および n はグリッドの寸法です。
• ガードビジョンのマーキング: 各ガードは、最大でも 4 方向の行または列の長さをチェックします。したがって、各ガードについては、O(m n).
となります。
• 保護されていないセルの数: O(m * n).

したがって、全体的な複雑さは O(m * n) となり、問題の制約を考慮すると効率的です。

エッジケース:

• ガードや壁が存在しない場合、グリッド全体がガードされなくなります。
• すべてのセルがガードまたは壁の場合、結果はガードされていないセルが 0 になります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がグリッド内の保護されていないセルを数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。