コミュニティ
学ぶ
ツールライブラリ
AIツール
レジャー
検索
日本語
ホームページ バックエンド開発 PHPチュートリアル 最高峰の地図

最高峰の地図

Barbara Streisand
Barbara Streisand
Jan 23, 2025 am 02:23 AM

1765年。最高峰の地図

難易度: 中

トピック: 配列、幅優先検索、行列

陸地と水セルの地図を表すサイズ m x n の整数行列 isWater が与えられます。

  • isWater[i][j] == 0 の場合、セル (i, j) は陸上セルです。
  • isWater[i][j] == 1 の場合、セル (i, j) は水のセルです。

次のルールに従って各セルに高さを割り当てる必要があります:

  • 各セルの高さは負であってはなりません。
  • セルが 水 セルの場合、その高さは 0 でなければなりません。
  • 隣接する 2 つのセルの絶対高さの差は 最大でも 1 でなければなりません。セルが別のセルの真北、東、南、または西にある場合 (つまり、彼らの側面は接触しています)。

行列の最大高さが最大化となるような高さの割り当てを見つけます。

サイズ m x n の整数行列の高さを返します。ここで、height[i][j] はセル (i, j) の高さです。複数の解がある場合は、いずれかを返します。

例 1:

最高峰の地図

  • 入力: isWater = [[0,1],[0,0]]
  • 出力: [[1,0],[2,1]]
  • 説明: 画像は、各セルに割り当てられた高さを示しています。
    • 青いセルは水のセル、緑のセルは陸のセルです。

例 2:

最高峰の地図

  • 入力: isWater = [[0,0,1],[1,0,0],[0,0,0]]
  • 出力: [[1,1,0],[0,1,1],[1,2,2]]
  • 説明: 高さ 2 は、割り当ての最大可能高さです。
    • ルールを満たしていれば、最大高さが 2 である高さの割り当ても受け入れられます。

例 3:

  • 入力: isWater = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0 ,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0 ,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0 ,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0 ,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0, 0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0 ,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1 ,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0, 0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1, 0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1 ,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0 ,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0, 0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1 ,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0, 1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0] 、[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1 ,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 ,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0, 0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1 ,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0 ,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0, 1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1, 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1 ,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1 ,0,1,1,0,0,0,0,1,0,1,0,0],...]
  • 出力: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1, 2,1,1,2,2,1,0 ,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1 、1、2、1、0、1、2、 3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1, 2,1,0,1,1,0,1 ,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1 、1、0、1、1、2、1、 0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0, 1,1,0,1,0,1,0 ,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2 、3、2、3、3、2、1、 0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1, 0,1,1,0,1,2]、 [0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1 ,0,0,1,1,0,0, 1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0, 0,1,2,1,0,1,2 ,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1 、1、1、1、0、1、0、 1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0, 1,1,1,0,1,0,1 ,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1 ,0,0,1,1,1,0, 0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1, 2,1,2,3,3,2,1 ,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0 、1、2、1、2、3]、[ 1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2, 1,1,0,1,1,1,1 ,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1 ,2,1,...]]

制約:

  • m == isWater.length
  • n == isWater[i].length
  • 1
  • isWater[i][j] は 0 または 1 です。
  • 水セルは少なくとも 1 つ あります。

ヒント:

  1. 各水セルを 0 に設定します。各セルの高さは、最も近い水セルによって制限されます。
  2. すべての水セルをソースとして使用してマルチソース BFS を実行します。

注: この質問は 542.01 マトリックスと同じです

解決策:

幅優先検索 (BFS) アプローチを使用できます。これに段階的にアプローチする方法を次に示します:

問題の内訳:

  1. 水のセル: 1 のセルは水のセルを表し、その高さは常に 0 です。
  2. 陸上セル: 0 のセルは陸上セルを表し、隣接する陸上セルの高さの差が最大 1 になるように高さを割り当てる必要があります。

アプローチ：

  1. BFS 初期化:

    • まず、すべての水のセル (値 1 のセル) を BFS の開始点としてマークし、それらの高さを 0 に割り当てます。
    • 次に、隣接する土地セル (値 0 のセル) を処理して高さを割り当てます。

  2. BFS トラバーサル:

    • 各水セルから外側に拡張し、隣接する陸セルごとに高さを 1 ずつ増やし、隣接するセル間の高さの差が 1 を超えないようにします。
    • すべてのセルが訪問されるまでこのプロセスを続けます。

  3. 結果: 結果は、指定されたルールに準拠し、高さの値が最大化された高さの行列になります。

このソリューションを PHP で実装してみましょう: 1765。最高峰の地図

<?php /**
 * @param Integer[][] $isWater
 * @return Integer[][]
 */
function highestPeak($isWater) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$$isWater1 = [[0,1],[0,0]];
$$isWater2 = [[0,0,1],[1,0,0],[0,0,0]];
$$isWater3 = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0],...];

echo highestPeak($$isWater1) . "\n"; // Output: [[1,0],[2,1]]
echo highestPeak($$isWater2) . "\n"; // Output: [[1,1,0],[0,1,1],[1,2,2]]
echo highestPeak($$isWater3) . "\n"; // Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1,2,1,1,2,2,1,0,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1,1,2,1,0,1,2,3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1,2,1,0,1,1,0,1,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,1,1,2,1,0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2,3,2,3,3,2,1,0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1,0,1,1,0,1,2],[0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0,0,1,2,1,0,1,2,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,1,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1,2,1,2,3,3,2,1,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0,1,2,1,2,3],[1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2,1,1,0,1,1,1,1,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1,2,1,...]]
?>
ログイン後にコピー

説明：

  1. 初期化:

    • すべてのセルの高さ行列を -1 で初期化します。水のセルはすぐに 0 に設定されます。
    • 水セルは BFS キューに登録されます。

  2. BFS:

    • 各セルをデキューしてキューを処理し、隣接するセルごとに、それが境界内にあるか、未訪問であるかを確認します。
    • それが有効な陸上セル (未訪問) の場合、現在のセルの高さより 1 つ大きい高さを割り当て、さらなる処理のためにキューに入れます。

  3. 結果:

    • BFS が完了すると、高さマトリックスには、指定された制約に従って、各セルの可能な最高の高さが含まれます。

時間計算量:

  • O(m * n) ここで、m は行数、n は列数です。これは、各セルが BFS トラバーサル中に最大 1 回処理されるためです。

このソリューションにより、マトリックスが正しい高さで満たされることが保証され、BFS は隣接するセル間の高さの差の制約を維持しながら各セルの最大高さを保証します。

連絡先リンク

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

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

  • LinkedIn
  • GitHub

以上が最高峰の地図の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

もっと見る

人気の記事

<🎜>：庭を育てる - 完全な突然変異ガイド
3週間前 By DDD
<🎜>：バブルガムシミュレーターインフィニティ - ロイヤルキーの取得と使用方法
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
KB5055612を修正する方法Windows 10にインストールできませんか？
3週間前 By DDD
Nordhold：Fusion System、説明
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
マンドラゴラ：魔女の木のささやき - グラップリングフックのロックを解除する方法
3週間前 By 尊渡假赌尊渡假赌尊渡假赌
もっと見る

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

もっと見る

ホットトピック

Java チュートリアル
1666
14
CakePHP チュートリアル
1426
52
Laravel チュートリアル
1328
25
PHP チュートリアル
1273
29
C# チュートリアル
1254
24
もっと見る
Related knowledge
PHPでの安全なパスワードハッシュ（例：Password_hash、password_verify）を説明します。 MD5またはSHA1を使用してみませんか？ PHPでの安全なパスワードハッシュ（例：Password_hash、password_verify）を説明します。 MD5またはSHA1を使用してみませんか？ Apr 17, 2025 am 12:06 AM

PHPでは、Password_hashとpassword_verify関数を使用して安全なパスワードハッシュを実装する必要があり、MD5またはSHA1を使用しないでください。 1）password_hashセキュリティを強化するために、塩値を含むハッシュを生成します。 2）password_verifyハッシュ値を比較して、パスワードを確認し、セキュリティを確保します。 3）MD5とSHA1は脆弱であり、塩の値が不足しており、最新のパスワードセキュリティには適していません。

PHPとPython：2つの一般的なプログラミング言語を比較します PHPとPython：2つの一般的なプログラミング言語を比較します Apr 14, 2025 am 12:13 AM

PHPとPythonにはそれぞれ独自の利点があり、プロジェクトの要件に従って選択します。 1.PHPは、特にWebサイトの迅速な開発とメンテナンスに適しています。 2。Pythonは、データサイエンス、機械学習、人工知能に適しており、簡潔な構文を備えており、初心者に適しています。

PHP：Web開発の重要な言語 PHP：Web開発の重要な言語 Apr 13, 2025 am 12:08 AM

PHPは、サーバー側で広く使用されているスクリプト言語で、特にWeb開発に適しています。 1.PHPは、HTMLを埋め込み、HTTP要求と応答を処理し、さまざまなデータベースをサポートできます。 2.PHPは、ダイナミックWebコンテンツ、プロセスフォームデータ、アクセスデータベースなどを生成するために使用され、強力なコミュニティサポートとオープンソースリソースを備えています。 3。PHPは解釈された言語であり、実行プロセスには語彙分析、文法分析、編集、実行が含まれます。 4.PHPは、ユーザー登録システムなどの高度なアプリケーションについてMySQLと組み合わせることができます。 5。PHPをデバッグするときは、error_reporting（）やvar_dump（）などの関数を使用できます。 6. PHPコードを最適化して、キャッシュメカニズムを使用し、データベースクエリを最適化し、組み込み関数を使用します。 7

アクション中のPHP：実際の例とアプリケーション アクション中のPHP：実際の例とアプリケーション Apr 14, 2025 am 12:19 AM

PHPは、電子商取引、コンテンツ管理システム、API開発で広く使用されています。 1）eコマース：ショッピングカート機能と支払い処理に使用。 2）コンテンツ管理システム：動的コンテンツの生成とユーザー管理に使用されます。 3）API開発：RESTFUL API開発とAPIセキュリティに使用されます。パフォーマンスの最適化とベストプラクティスを通じて、PHPアプリケーションの効率と保守性が向上します。

スカラータイプ、リターンタイプ、ユニオンタイプ、ヌル可能なタイプなど、PHPタイプのヒントはどのように機能しますか？ スカラータイプ、リターンタイプ、ユニオンタイプ、ヌル可能なタイプなど、PHPタイプのヒントはどのように機能しますか？ Apr 17, 2025 am 12:25 AM

PHPタイプは、コードの品質と読みやすさを向上させるためのプロンプトがあります。 1）スカラータイプのヒント：php7.0であるため、基本データ型は、int、floatなどの関数パラメーターで指定できます。 3）ユニオンタイプのプロンプト：PHP8.0であるため、関数パラメーターまたは戻り値で複数のタイプを指定することができます。 4）Nullable Typeプロンプト：null値を含めることができ、null値を返す可能性のある機能を処理できます。

PHPの永続的な関連性：それはまだ生きていますか？ PHPの永続的な関連性：それはまだ生きていますか？ Apr 14, 2025 am 12:12 AM

PHPは依然として動的であり、現代のプログラミングの分野で重要な位置を占めています。 1）PHPのシンプルさと強力なコミュニティサポートにより、Web開発で広く使用されています。 2）その柔軟性と安定性により、Webフォーム、データベース操作、ファイル処理の処理において顕著になります。 3）PHPは、初心者や経験豊富な開発者に適した、常に進化し、最適化しています。

PHP対その他の言語：比較 PHP対その他の言語：比較 Apr 13, 2025 am 12:19 AM

PHPは、特に迅速な開発や動的なコンテンツの処理に適していますが、データサイエンスとエンタープライズレベルのアプリケーションには良くありません。 Pythonと比較して、PHPはWeb開発においてより多くの利点がありますが、データサイエンスの分野ではPythonほど良くありません。 Javaと比較して、PHPはエンタープライズレベルのアプリケーションでより悪化しますが、Web開発により柔軟性があります。 JavaScriptと比較して、PHPはバックエンド開発により簡潔ですが、フロントエンド開発のJavaScriptほど良くありません。

PHPおよびPython：さまざまなパラダイムが説明されています PHPおよびPython：さまざまなパラダイムが説明されています Apr 18, 2025 am 12:26 AM

PHPは主に手順プログラミングですが、オブジェクト指向プログラミング（OOP）もサポートしています。 Pythonは、OOP、機能、手続き上のプログラミングなど、さまざまなパラダイムをサポートしています。 PHPはWeb開発に適しており、Pythonはデータ分析や機械学習などのさまざまなアプリケーションに適しています。

See all articles