118 Mutant Flatworld Explorers

題目連結

題目敘述

在一個矩形網格上，每個機器人從一個初始位置開始，根據指令移動，請模擬它們的最終位置。 機器人位置由一對整數座標 (x, y) 和一個方向（N、S、E、W）組成。 (x, y) 的北方為 (x, y + 1)

指令 :

• L : 向左轉 90 度，不改變位置。
• R : 向右轉 90 度，不改變位置。
• F : 往目前面向的方向前進一格，方向不變。

規則 :

• 地圖是矩形且有邊界，若機器人前進導致超出邊界，該機器人會永遠遺失（LOST）。

• 當一個機器人遺失時，它會在最後所在的合法位置留下氣味（scent）。

• 未來的機器人如果從這個留下氣味的位置收到同樣會導致掉落的 F 指令，則該指令會被忽略（避免再次掉落），但其他指令仍照常執行。

輸入格式

• 第一行為網格右上角的座標 X Y（左下角預設為 0 0）

接下來每兩行描述一台機器人，有多個機器人：

• 第一行：初始座標 x y 與初始方向 O（N、E、S、W）
• 第二行：一串指令，由 L（左轉）、R（右轉）、F（前進）組成

輸出格式

每台機器人最終停留的座標 x y 與朝向 O。

若機器人掉出邊界，則在最後加上 LOST。

解題思路

模擬機器人路徑，若座標在 scent 則忽略此指令，若掉出邊界將座標加入 scent。

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
  int maxX, maxY;
  cin >> maxX >> maxY;

  set<pair<int, int>> scent;

  int curX, curY;
  string orientation, commands;

  while (cin >> curX >> curY >> orientation >> commands) {
    bool isLost = false;

    for (char command : commands) {
      int prevX = curX, prevY = curY;
      string prevOrientation = orientation;

      if (command == 'L') {
        if (orientation == "N")
          orientation = "W";
        else if (orientation == "W")
          orientation = "S";
        else if (orientation == "S")
          orientation = "E";
        else if (orientation == "E")
          orientation = "N";
      } else if (command == 'R') {
        if (orientation == "N")
          orientation = "E";
        else if (orientation == "E")
          orientation = "S";
        else if (orientation == "S")
          orientation = "W";
        else if (orientation == "W")
          orientation = "N";
      } else if (command == 'F') {
        if (orientation == "N")
          curY++;
        else if (orientation == "E")
          curX++;
        else if (orientation == "S")
          curY--;
        else if (orientation == "W")
          curX--;
      }

      if (curX < 0 || curX > maxX || curY < 0 || curY > maxY) {
        if (scent.count({prevX, prevY})) {
          curX = prevX;
          curY = prevY;
        } else {
          isLost = true;
          scent.insert({prevX, prevY});
          curX = prevX;
          curY = prevY;
          break;
        }
      }
    }

    cout << curX << " " << curY << " " << orientation;
    if (isLost) cout << " LOST";
    cout << "\n";
  }

  return 0;
}