โปรแกรม C++ ค้นหาการเคลื่อนไหวเพื่ออ่านจุดจากจุดอื่นในระนาบ 2 มิติ

สมมติว่ามีจุดสองจุดในระนาบ 2 มิติ a และ b ที่มีพิกัด (x1, y1) และ (x2, y2) ตามลำดับ ขณะนี้เราอยู่ที่จุด 'a' และสามารถเคลื่อนที่ได้ในระยะ 1 ทั้งในแนวตั้งหรือแนวนอน เราย้ายไปยังจุด b จากจุด a จากนั้นกลับไปที่จุด a และเราไปที่จุด b อีกครั้ง ไม่อนุญาตให้เคลื่อนที่ผ่านจุดเดียวกันมากกว่าหนึ่งครั้ง ยกเว้นจุด a และ b เราต้องค้นหาการเคลื่อนไหวที่เราจะทำในทริปนี้ทั้งหมดและแสดงออกมา ถ้าเราเคลื่อนไปทางขวา เราจะพิมพ์ 'R', 'L' หากเราเลื่อนไปทางซ้าย, 'U' หากเราเลื่อนขึ้น และ 'D' หากเราเลื่อนลง สิ่งหนึ่งที่เราต้องสังเกตก็คือ x2> x1 และ y2> y1

ดังนั้น หากอินพุตเป็น x1 =0, y1 =1, x2 =3, y2 =4 ดังนั้นเอาต์พุตจะเป็น UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

s := a blank string
for initialize i := 0, when i < y2 - y1, update (increase i by 1), do:
   add "U" at the end of s
for initialize i := 0, when i < x2 - x1, update (increase i by 1), do:
   add "R" at the end of s
for initialize i := 0, when i < y2 - y1, update (increase i by 1), do:
   add "D" at the end of s
for initialize i := 0, when i < x2 - x1, update (increase i by 1), do:
   add "L" at the end of s
   add "LU" at the end of s
for initialize i := 0, when i < y2 - y1, update (increase i by 1), do:
   add "U" at the end of s
for initialize i := 0, when i < x2 - x1, update (increase i by 1), do:
   add "R" at the end of s
   add "RD" at the end of s
   add "RD" at the end of s
for initialize i := 0, when i < y2 - y1, update (increase i by 1), do:
   add "D" at the end of s
for initialize i := 0, when i < x2 - x1, update (increase i by 1), do:
   add "L" at the end of s
   add "LU" at the end of s
return s

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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.append("U");
   for(int i = 0; i < x2 - x1; i++)
      s.append("R");
   for(int i = 0; i < y2 - y1; i++)
      s.append("D");
   for(int i = 0; i < x2 - x1; i++)
      s.append("L");
   s.append("LU");
   for(int i = 0; i < y2 - y1; i++)
      s.append("U");
   for(int i = 0; i < x2 - x1; i++)
      s.append("R");
      s.append("RD");
      s.append("RD");
   for(int i = 0; i < y2 - y1; i++)  
      s.append("D");
   for(int i = 0; i < x2 - x1; i++) s.append("L");
      s.append("LU");
   return s;
}
int main() {
   int x1 = 0, y1 = 1, x2 = 3, y2 = 4; cout<< solve(x1, y1, x2, y2);
   return 0;
}

อินพุต

0, 1, 3, 4

ผลลัพธ์

UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU