Số điểm dừng tối thiểu từ đường đi cho trước trong C++

Đề bài

• Có nhiều điểm trong không gian hai chiều cần thăm theo thứ tự cụ thể.
• Đường đi từ điểm này đến điểm khác luôn chọn đường ngắn nhất và các đoạn đường luôn song song với đường lưới.
• Cho đường đi được chọn để thăm các điểm. Cần cho biết số điểm tối thiểu cần thiết để tạo ra đường đi cho trước.

Thuật toán

1. Có thể giải bài toán bằng cách quan sát mẫu di chuyển khi thăm điểm dừng.
2. Nếu muốn đi đường ngắn nhất từ điểm này đến điểm khác, sẽ di chuyển theo một hoặc tối đa hai hướng.

Ví dụ mã 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 << "Số điểm dừng tối thiểu = " << getMinStops(path) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số điểm dừng tối thiểu = 3