CSES - Grid Path Construction | Xây dựng Đường đi trên Lưới

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 2200 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một lưới \(n \times m\) và hai ô vuông \(a = (y_1, x_1)\)\(b = (y_2, x_2)\), hãy tạo một đường đi từ \(a\) đến \(b\) mà đi qua mỗi ô vuông đúng một lần.

Ví dụ, đây là một đường đi từ \(a = (1, 3)\) đến \(b = (3, 6)\) trên một lưới \(4 \times 7\):

Input

Dòng đầu vào đầu tiên có một số nguyên \(t\): số lượng test.

Sau đó, có \(t\) dòng mô tả các test. Mỗi dòng có sáu số nguyên \(n\), \(m\), \(y_1\), \(x_1\), \(y_2\)\(x_2\).

Trong tất cả test \(1 \leq y_1, y_2 \leq n\)\(1 \leq x_1, x_2, \leq m\). Thêm vào đó, \(y_1 \neq y_2\) hoặc \(x_1 \neq x_2\).

Output

In ra YES, nếu có thể xây dựng một đường đi, và NO nếu ngược lại.

Nếu có một đường đi, hãy in thêm mô tả của nó bao gồm các kí tự U (lên), D (xuống), L (trái) và R (phải). Nếu có nhiều đường đi, bạn có thể in ra bất kì trong số chúng.

Giới hạn

  • \(1 \leq t \leq 100\)
  • \(1 \leq n \leq 50\)
  • \(1 \leq m \leq 50\)

Ví dụ

Input:

5  
1 3 1 1 1 3  
1 3 1 2 1 3  
2 2 1 1 2 2  
2 2 1 1 2 1  
4 7 1 3 3 6

Output:

YES  
RR  
NO  
NO  
YES  
RDL  
YES  
RRRRDDDLLLLLLUUURDDRURDRURD