#include using namespace std; using edge = tuple; const vector dx{1, 0, -1, 0, 1, 0, -1, 0}, dy{0, 1, 0, -1, 0, 1, 0, -1}; const string ds{'D', 'R', 'U', 'L', 'D', 'R', 'U', 'L'}; random_device rng; int h, w, p; bool in_board(int x, int y) { return 0 <= x and x < h and 0 <= y and y < w; } int main() { cin >> h >> w >> p; vector cost_h(h, vector(w - 1, 1000)); vector cost_v(h - 1, vector(w, 1000)); while (true) { vector dist(h, vector(w, 1e18)); priority_queue, greater> q; q.emplace(0, 0, 0); while (not q.empty()) { auto [d0, x0, y0]{q.top()}; q.pop(); if (d0 >= dist[x0][y0]) continue; dist[x0][y0] = d0; for (int i = 0; i < 4; i++) { int x = x0 + dx[i], y = y0 + dy[i]; if (not in_board(x, y)) continue; int64_t c; if (i % 2 == 0) { c = cost_v.at(x0 - i / 2).at(y0); } else { c = cost_h.at(x0).at(y0 - i / 2); } int64_t d = d0 + c; if (d >= dist[x][y]) continue; q.emplace(d, x, y); } } vector dirs; string ans; int x0 = h - 1, y0 = w - 1; while (x0 or y0) { int d0 = dist[x0][y0]; vector ok; for (int i = 0; i < 4; i++) { int x = x0 + dx[i], y = y0 + dy[i]; if (not in_board(x, y)) continue; int64_t c; if (i % 2 == 0) { c = cost_v[x0 - i / 2][y0]; } else { c = cost_h[x0][y0 - i / 2]; } int64_t d = d0 - c; if (d != dist[x][y]) continue; ok.emplace_back((i + 2) % 4); } int sz = ok.size(); int d = ok.at(rng() % sz); dirs.emplace_back(d); ans += ds[d]; x0 -= dx[d]; y0 -= dy[d]; } reverse(dirs.begin(), dirs.end()); reverse(ans.begin(), ans.end()); cout << ans << endl; int res; cin >> res; if (res == -1) { break; } for (int i = 0; i < res; i++) { int d = dirs[i]; int x = x0 + dx[d], y = y0 + dy[d]; if (d % 2 == 0) { cost_v[x0 - d / 2][y0] = 1; } else { cost_h[x0][y0 - d / 2] = 1; } x0 = x; y0 = y; } if (int(ans.size()) > res) { int d = dirs[res]; int x = x0 + dx[d], y = y0 + dy[d]; if (d % 2 == 0) { if (cost_v[x0 - d / 2][y0] == 1) continue; cost_v[x0 - d / 2][y0] += 10000; } else { if (cost_h[x0][y0 - d / 2] == 1) continue; cost_h[x0][y0 - d / 2] += 10000; } x0 = x; y0 = y; } for (int i = res + 1; i < int(ans.size()); i++) { int d = dirs[i]; int x = x0 + dx[d], y = y0 + dy[d]; if (d % 2 == 0) { if (cost_v[x0 - d / 2][y0] == 1) continue; cost_v[x0 - d / 2][y0] += 1; } else { if (cost_h[x0][y0 - d / 2] == 1) continue; cost_h[x0][y0 - d / 2] += 1; } x0 = x; y0 = y; } } return 0; }