โปรแกรม C++ หาลำดับการเคลื่อนที่ระหว่างจุดสองจุดบนมิติ 2

มีจุด a(x1,y1) และ b(x2,y2) โดย x2>x1, y2>y1 เริ่มที่ a เดินไป b กลับ a ไป b อีกครั้ง เดินทีละ 1 หน่วย แนวนอน/แนวตั้ง ห้ามผ่านจุดเดิมซ้ำ (ยกเว้น a,b) ต้องการสตริงการเคลื่อนที่: R ขวา, L ซ้าย, U บน, D ล่าง

ตัวอย่าง: x1=0,y1=1,x2=3,y2=4 ผลลัพธ์: UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU

ขั้นตอนการแก้ปัญหา (สร้างสตริงตามรูปแบบคงที่)

1. U จำนวน y2-y1 ครั้ง (ขึ้น)
2. R จำนวน x2-x1 ครั้ง (ขวา) → ถึง b ครั้งแรก
3. D จำนวน y2-y1 ครั้ง (ลง)
4. L จำนวน x2-x1 ครั้ง (ซ้าย) → กลับ a ครั้งแรก
5. LU (ซ้าย 1, ขึ้น 1) → เลี่ยงนอก
6. U จำนวน y2-y1 ครั้ง
7. R จำนวน x2-x1 ครั้ง → ถึง b ครั้งที่สอง
8. RD RD (ขวา1ลง1 สองครั้ง)
9. D จำนวน y2-y1 ครั้ง
10. L จำนวน x2-x1 ครั้ง → กลับ a ครั้งที่สอง
11. LU จบ

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

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

string solve(int x1, int y1, int x2, int y2) {
    string s = "";
    for (int i = 0; i < y2 - y1; i++) s += "U";
    for (int i = 0; i < x2 - x1; i++) s += "R";
    for (int i = 0; i < y2 - y1; i++) s += "D";
    for (int i = 0; i < x2 - x1; i++) s += "L";
    s += "LU";
    for (int i = 0; i < y2 - y1; i++) s += "U";
    for (int i = 0; i < x2 - x1; i++) s += "R";
    s += "RD"; s += "RD";
    for (int i = 0; i < y2 - y1; i++) s += "D";
    for (int i = 0; i < x2 - x1; i++) s += "L";
    s += "LU";
    return s;
}

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

อินพุต / เอาต์พุต

Input: 0, 1, 3, 4

Output: UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU