CSES 2418 - Grid Path Construction

給定一個 \(n \times m\) 的方格盤與兩個格子 \(a=(y_1,x_1)\) 和 \(b=(y_2,x_2)\)，請造出一條從 \(a\) 到 \(b\) 的路徑，使它恰好經過每個格子一次。

舉例來說，以下是一個 \(4 \times 7\) 方格盤中從 \(a=(1,3)\) 到 \(b=(3,6)\) 的路徑：

輸入格式

第一行有一個整數 \(t\)：測試的筆數。

接下來有 \(t\) 行描述這些測試，每行有六個整數 \(n\)、\(m\)、\(y_1\)、\(x_1\)、\(y_2\) 和 \(x_2\)。

所有測試都滿足 \(1 \le y_1,y_2 \le n\) 以及 \(1 \le x_1,x_2 \le m\)。此外，\(y_1 \neq y_2\) 或 \(x_1 \neq x_2\)。

輸出格式

若可以造出路徑就輸出 YES，否則輸出 NO。

若存在路徑，接著再輸出它的描述，由字元 U（上）、D（下）、L（左）與 R（右）組成。若有多條路徑，輸出任何一條都可以。

範例輸入 1

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

範例輸出 1

YES
RR
NO
NO
YES
RDL
YES
RRRRDDDLLLLLLUUURDDRURDRURD

限制

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

題目來源

CSES - Grid Path Construction

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。