Go and Back


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type

Vincent đang đứng tại một điểm trên mặt phẳng tọa độ Oxy. Vị trí hiện tại mà anh ta đang đứng đó là S (S_x , S_y) với mỗi một lượt di chuyên, anh ta có thể đi sang trái, phải, lên, xuống trên mặt phẳng tọa độ với độ dài là 1. Chú ý các toạn độ đều là số nguyên.

Bài toán đặt ra là: Đầu tiên Vincent sẽ đi đến điểm T (T_x , T_y) với \((S_x < T_x và S_y < T_y)\), tiếp sau đó sẽ quay trở lại điểm S rồi lại đến điểm T một lần nữa và cuối cùng lại quay trở lại điểm S. Nhiệm vụ của bạn là hãy đường đi ngắn nhất cho Vincent sao cho trong suốt quá trình di chuyển anh ta không đi qua bất kỳ điểm nào đã đến trước đó (mỗi điểm đi qua đúng 1 lần).

Input:

  • Một dòng gồm 4 số nguyên S_x , S_y , T_x , T_y với ( -1000 \le S_x \le T_X \le 10^{10})( -1000 \le S_y \le T_y \le 10^{10})

Output:

  • In ra một chuỗi đường đi ngắn nhất cho Vincent
  • Mỗi ký tự của đầu ra tương ứng với bước di chuyển của anh ta: U -> Lên, D -> Xuống, L -> Trái, R -> Phải.

Example:

Input 1:

0 0 1 2

Output 1:

UURDDLLUUURRDRDDDLLU

Giải thích

  • Từ (0, 0) đến (1, 2) lần đầu : (0,0) → (0,1) → (0,2) → (1,2)
  • Từ (1, 2) đến (0, 0) lần đầu : (1,2) → (1,1) → (1,0) → (0,0)
  • Từ (0, 0) đến (1, 2) lần hai : (0,0) → (−1,0) → (−1,1) → (−1,2) → (−1,3) → (0,3) → (1,3) → (1,2)
  • Từ (1, 2) đến (0, 0) lần hai : (1,2) → (2,2) → (2,1) → (2,0) → (2,−1) → (1,−1) → (0,−1) → (0,0)

Comments

There are no comments at the moment.