。歩行ロボットシミュレーション

874。歩行ロボットシミュレーション

難易度: 中

トピック: 配列、ハッシュ テーブル、シミュレーション

無限 XY 平面上のロボットは、北を向いた点 (0, 0) から開始します。ロボットは、次の 3 種類のコマンドのシーケンスを受け取ることができます:

• -2: 左に90度回転します。
• -1: 右に 90 度回転します。
• 1

グリッドのマス目の一部は障害物です。 i 番目の障害物は格子点障害物[i] = (x_i, y_i)にあります。ロボットが障害物に遭遇した場合、ロボットは現在の位置に留まり、次のコマンドに進みます。

ロボットが原点から取得する 最大ユークリッド距離を 二乗 で返します (つまり、距離が 5 の場合は 25 を返します)。

注:

• 北とは +Y 方向を意味します。
• 東は +X 方向を意味します。
• 南は -Y 方向を意味します。
• 西とは -X 方向を意味します。
• [0,0] に障害物がある可能性があります。

例 1:

• 入力: コマンド = [4,-1,3]、障害物 = []
• 出力: 25
• 説明: ロボットは (0, 0) から開始します。
  1. (0, 4) まで北に 4 単位移動します。
  2. 右折してください。
  3. 東に 3 ユニット移動して (3, 4) に移動します。
  4. ロボットが原点からこれまでに到達した最も遠い点は (3, 4) で、その 2 乗は 32 + 42 = 25 単位離れています。

例 2:

• 入力: コマンド = [4,-1,4,-2,4]、障害物 = [[2,4]]
• 出力: 65
• 説明: ロボットは (0, 0) から開始します。
  1. (0, 4) まで北に 4 単位移動します。
  2. 右折してください。
  3. 東に 1 ユニット移動すると (2, 4) の障害物にブロックされます。ロボットは (1, 4) にいます。
  4. 左折してください。
  5. 北に 4 単位移動して (1, 8) に移動します。
  6. ロボットがこれまでに原点から到達した最も遠い点は (1, 8) であり、その 2 乗は 12 + 82 = 65 単位離れています。

例 3:

• 入力: コマンド = [6,-1,-1,6]、障害物 = []
• 出力: 36
• 説明: ロボットは (0, 0) から開始します。
  1. (0, 6) まで北に 6 単位移動します。
  2. 右折してください。
  3. 右折してください。
  4. 南に 6 ユニット移動して (0, 0) に移動します。
  5. ロボットが原点から到達した最も遠い点は (0, 6) で、その 2 乗は 62 = 36 単位離れています。

制約:

• 1 4
• コマンド[i]は、-2、-1、または範囲[1, 9]の整数です。
• 0 4
• -3 * 10⁴ i, y_i 4
• 答えは 2³¹ 未満であることが保証されています

解決策:

一連のコマンドに基づいて無限の 2D グリッド上でロボットの動きをシミュレートし、障害物がある場合はそれを回避する必要があります。目標は、ロボットが原点から到達する最大ユークリッド距離の 2 乗を決定することです。

アプローチ

1. 方向処理:

   • ロボットは、北、東、南、西の 4 つの方向のいずれかを向くことができます。
   • これらの方向はベクトルとして表すことができます。
     • 北: (0, 1)
     • 東: (1, 0)
     • 南: (0, -1)
     • 西: (-1, 0)

2. 方向転換:

   • 左折 (-2) と方向が反時計回りに 90 度変わります。
   • 右折 (-1) すると、方向が時計回りに 90 度変わります。

3. 動き:

   • 移動コマンドごとに、ロボットは現在の方向に一度に 1 ユニットずつ移動します。障害物に遭遇すると、そのコマンドに対して動きを停止します。

4. 障害物の追跡:

   • 迅速な検索のために障害物リストをタプルのセットに変換し、ロボットが障害物に衝突するかどうかを迅速に判断できるようにします。

5. 距離計算:

   • ロボットが動作中に到達する原点からの最大二乗距離を追跡します。

このソリューションを PHP で実装してみましょう: 874。歩行ロボットシミュレーション

<?php
/**
 * @param Integer[] $commands
 * @param Integer[][] $obstacles
 * @return Integer
 */
function robotSim($commands, $obstacles) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo robotSim([4,-1,3], []) . "\n"; // Output: 25
echo robotSim([4,-1,4,-2,4], [[2,4]]) . "\n"; // Output: 65
echo robotSim([6,-1,-1,6], []) . "\n"; // Output: 36
?>

説明：

• 方向管理: ベクトルのリストを使用して方向を表すため、移動後の次の位置を簡単に計算できます。
• 障害物検出: 障害物をセットに保存することで、位置が障害物によってブロックされているかどうかを確認するための時間計算量は O(1) になります。
• 距離計算: ロボットが移動する際に到達する最大二乗距離を継続的に更新します。

テストケース

• 提供されているサンプル テスト ケースは、ソリューションを検証するために使用されます。
  • 障害物がない [4,-1,3] は 25 を返すはずです。
  • [4,-1,4,-2,4] に障害物 [[2,4]] がある場合、65 が返されるはずです。
  • 障害物がない場合、[6,-1,-1,6] は 36 を返すはずです。

このソリューションは問題の制約を効率的に処理し、必要に応じて最大距離の二乗を計算します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が。歩行ロボットシミュレーションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。