จำนวนสถานีต่ำสุดจากเส้นทางที่กำหนดใน C++

ข้อกำหนดโจทย์

• มีจุดมากมายในพื้นที่สองมิติที่ต้องเยี่ยมชมในลำดับเฉพาะ
• เส้นทางจากจุดหนึ่งไปอีกจุดหนึ่งจะเลือกเป็นเส้นทางสั้นที่สุดเสมอ และส่วนของเส้นทางจะจัดเรียงตามเส้นกริดเสมอ
• เราได้รับเส้นทางที่เลือกสำหรับการเยี่ยมชมจุด เราต้องบอกจำนวนจุดขั้นต่ำที่จำเป็นต้องสร้างเส้นทางที่กำหนด

อัลกอริทึม

1. เราสามารถแก้ปัญหานี้ได้โดยสังเกตรูปแบบการเคลื่อนที่เมื่อเยี่ยมชมสถานี
2. หากเราต้องการใช้เส้นทางสั้นที่สุดจากจุดหนึ่งไปอีกจุด เราจะเคลื่อนที่ในทิศทางเดียวหรือสูงสุดสองทิศทาง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
  int n = path.length();
  map<char, int> directionMap;
  int stops = 1;
  for (int i = 0; i < n; ++i) {
    char direction = path[i];
    directionMap[direction] = 1;
    if ((directionMap['L'] && directionMap['R']) || (directionMap['U'] && directionMap['D'])) {
      directionMap.clear();
      ++stops;
      directionMap[direction] = 1;
    }
  }
  return stops + 1;
}
int main() {
  string path = "LLUUULLDD";
  cout << "Minimum stops = " << getMinStops(path) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum stops = 3