Ruudukko

#include <bits/stdc++.h>
 
typedef long long ll;
 
#define M 1000000007
 
using namespace std;
 
bool vis[50][50];
string path;
string ans;
int n, m, y2, x2;
 
int dirs[4][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};
 
string pd = "DURL";
 
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
 
void rec(int y, int x, int steps) {
    if (vis[y][x] || ans != "X") return;
    if (steps + 1 == n*m) {
        if (y == y2 && x == x2) {
            ans = path;
        }
        return;
    }
 
    vis[y][x] = 1;
 
    for (int i = 0; i < 4; ++i) {
        int ty = y + dirs[i][0];
        int tx = x + dirs[i][1];
 
        path[steps] = pd[i];
 
        if (!inside(ty, tx)) continue;
 
        rec(ty, tx, steps + 1);
    }
    
    vis[y][x] = 0;
} 
 
void test_case() {
	int y1, x1;
	cin >> n >> m >> y1 >> x1 >> y2 >> x2;
 
    if (n == 1) {
        if (x1 == 1 && x2 == m) {
            cout << "YES\n";
            for (int i = 1; i < m; ++i) {
                cout << "R";
            }
        } else if (x1 == m && x2 == 1) {
            cout << "YES\n";
            for (int i = 1; i < m; ++i) {
                cout << "L";
            }
        } else {
            cout << "NO";
        }
        return;
    } 
    
    x1--; y1--; x2--; y2--;
    // Kuljetaan aina piiloon?
    path = ""; 
    ans = "X";
    for (int i = 1; i < n*m; ++i) path += "X";
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            vis[i][j] = 0;
        }
    }
 
    rec(y1, x1, 0); 
 
    if (ans == "X") {
        cout << "NO";
        return;
    }
    cout << "YES\n";
    cout << ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		test_case();
		cout << "\n";
	}
 
	return 0;
}
 
/*int px = x1;
    int py = y1;
 
    bool vis[51][51];
 
    for (int i = 0; i <= 50; ++i) {
        for (int j = 0; j <= 50; ++j) {
            vis[i][j] = 0;
        }
    }
 
    int dirs[4][2] = {
        {1, 0},
        {0, 1},
        {-1, 0},
        {0, -1}
    };
 
    int vt = 1;
 
    string path;
 
    string cd = "RDLU";
 
    while (vt + 1 < n*m) {
        // valitaan suunta
 
        int bd = 1e9;
        int bdx = 0, bdy = 0;
        char c;
        //cout << "at: " << py << ", " << px << endl;
        vis[py][px] = 1;
        int i = -1;
        for (auto d : dirs) {
            int tx = px + d[0];
            int ty = py + d[1];
            i++;
            if (tx < 1 || tx > m || ty < 1 || ty > n) continue;
            if (vis[ty][tx]) continue;
            if (tx == x2 && ty == y2) continue;
            int td = min(ty - 1, n - ty) + min(tx - 1, m - tx);
            if (td < bd) {
                c = cd[i];
                bd = td;
                bdx = d[0];
                bdy = d[1];
            }
            
        }
 
        //cout << "dif: " << bdy << ", " << bdx << endl;
 
        if (bd == 1e9) {
            cout << "NO";
            return;
        } else {
            px += bdx;
            py += bdy;
            path += c;
        }
        vt++;
    }
 
    if (px + 1 == x2) path += "R";
    else if (px - 1 == x2) path += "L";
    else if (py + 1 == y2) path += "D";
    else path += "U";
 
    cout << "YES\n";
    cout << path;*/

Test 1

Group: 1, 5

Verdict: ACCEPTED

Test 2

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 5

Verdict: ACCEPTED

Test 10

Group: 3, 5

Verdict: ACCEPTED

Test 11

Group: 3, 5

Verdict: ACCEPTED

Test 12

Group: 3, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED