Chương trình C++ tìm chuỗi di chuyển giữa hai điểm trên mặt phẳng 2D

Mô tả bài toán

Hai điểm a(x1,y1), b(x2,y2) với x2>x1, y2>y1. Từ a đi đến b, quay lại a, lại đi đến b. Chỉ đi ngang/dọc bước 1, không đi qua cùng điểm 2 lần (trừ a,b). Xuất chuỗi ký tự 'U','D','L','R'.

Ví dụ

x1=0,y1=1,x2=3,y2=4. Đầu ra: UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU.

Thuật toán (Xây dựng chuỗi theo mẫu cố định)

1. Đi từ a→b: U*(dy) R*(dx).
2. Quay lại b→a: D*(dy) L*(dx).
3. Lần 2 a→b: LU U*(dy) R*(dx) RD.
4. Quay lại lần 2: RD D*(dy) L*(dx) LU.
5. Ghép các đoạn theo thứ tự trên.

Đoạn mã C++

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

string solve(int x1,int y1,int x2,int y2){
    string s;
    int dx=x2-x1, dy=y2-y1;
    s.append(dy,'U');
    s.append(dx,'R');
    s.append(dy,'D');
    s.append(dx,'L');
    s+="LU";
    s.append(dy,'U');
    s.append(dx,'R');
    s+="RD";
    s+="RD";
    s.append(dy,'D');
    s.append(dx,'L');
    s+="LU";
    return s;
}

int main(){
    int x1=0,y1=1,x2=3,y2=4;
    cout << solve(x1,y1,x2,y2);
    return 0;
}

Đầu vào / Đầu ra

Input: 0, 1, 3, 4

Output: UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU