#include using namespace std; using ll = long long; using ld = long double; using Pair = pair; using Tuple = tuple; using VI1 = vector; using VI2 = vector; using VL1 = vector; using VL2 = vector; using VD1 = vector; using VD2 = vector; using VB1 = vector; using VB2 = vector; using VP1 = vector; using VP2 = vector; using VT1 = vector; using VT2 = vector; using Queue = queue; using DQ = deque; using PQ = priority_queue, greater>; using Table = VI2; using Graph = VI2; /** io */ template std::vector input_vec(int N); template void output_row(std::vector &row); template void output_col(std::vector &col); void outputYesNo(bool yes, const string &Yes = "Yes", const string &No = "No"); /** minmax */ template bool chmin(T &a, T b); template bool chmax(T &a, T b); using Cell = int; using Row = vector; using Grid = vector; Cell read_cell() { Cell cell; char c; cin >> c; cell = (c == '#') ? 1 : 0; return cell; } Grid read_grid(int H, int W) { Grid grid(H, Row(W)); for (auto &row : grid) { for (auto &cell : row) { cell = read_cell(); } } return grid; } bool is_out(int H, int W, int x, int y) { if (x < 0 || H <= x) return true; if (y < 0 || W <= y) return true; return false; } Grid rotate(Grid &org) { int H = org.size(); int W = org.front().size(); Grid rotated(W, Row(H)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { rotated[W - 1 - j][i] = org[i][j]; } } return rotated; } const vector dx{0, 0, -1, 1}, dy{-1, 1, 0, 0}; const string LRUD = "LRUD"; const int INF = 1001001001; Grid calc_cost(int H, int W, Grid &S, int sx, int sy) { Grid cost(H, Row(W, INF)); Queue que; cost[sx][sy] = 0; que.emplace(sx, sy); while (que.size()) { auto [x1, y1] = que.front(); que.pop(); for (int i = 0; i < 4; ++i) { auto x2 = x1 + dx[i], y2 = y1 + dy[i]; if (is_out(H, W, x2, y2)) continue; if (S[x2][y2] == 1) continue; if (chmin(cost[x2][y2], cost[x1][y1] + 1)) { que.emplace(x2, y2); } } } return cost; } string calc_route(int H, int W, Grid &S, Grid &cost, int sx, int sy) { string route; int len = cost[sx][sy]; for (int i = 0, x1 = sx, y1 = sy; i < len; ++i) { for (int j = 0; j < 4; ++j) { auto x2 = x1 + dx[j], y2 = y1 + dy[j]; if (is_out(H, W, x2, y2)) continue; if (S[x2][y2] == 1) continue; if (cost[x2][y2] == cost[x1][y1] - 1) { route += LRUD[j]; x1 = x2, y1 = y2; break; } } } return route; } void convert(string &T1) { reverse(T1.begin(), T1.end()); int len = T1.size(); for (int i = 0; i < len; ++i) { auto T1i = T1.at(i); if (T1i == 'L') T1[i] = 'R'; if (T1i == 'R') T1[i] = 'L'; if (T1i == 'U') T1[i] = 'D'; if (T1i == 'D') T1[i] = 'U'; } return; } auto solve(string &T) { int H, W, K, L, R; cin >> H >> W >> K >> L >> R; --L; auto S = read_grid(H, W); if ((R - L) % 2 == 1) return false; auto cost1 = calc_cost(H, W, S, 0, 0); auto cost2 = calc_cost(H, W, S, H - 1, W - 1); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (S[i][j] == 1) continue; if (cost1[i][j] > L || (L - cost1[i][j]) % 2 != 0) continue; if (cost2[i][j] > K - R || (K - R - cost2[i][j]) % 2 != 0) continue; int k0 = -1; for (int k = 0; k0 == -1 && k < 4; k += 2) { auto i2 = i + dx[k], j2 = j + dy[k]; auto i3 = i - dx[k], j3 = j - dy[k]; if (is_out(H, W, i2, j2)) continue; if (is_out(H, W, i3, j3)) continue; if (S[i2][j2] == 1) continue; k0 = k; } if (k0 == -1) continue; auto T1 = calc_route(H, W, S, cost1, i, j); auto T2 = calc_route(H, W, S, cost2, i, j); convert(T1); for (int k = 0; k < R - L; ++k) { T1.push_back(LRUD.at(k0 + k % 2)); } T = T1 + T2; return true; } } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { string T; auto result = solve(T); outputYesNo(result); if (result) { cout << T << '\n'; } // output_row(result); // output_col(result); // outputYesNo(result, "Yes", "No"); } } /** @note 使用頻度が高く毎回貼付するのが面倒なライブラリを実装しておく。*/ template std::vector input_vec(int N) { std::vector v(N); for (auto &vi : v) { cin >> vi; } return v; } void outputYesNo(bool yes, const string &Yes, const string &No) { if (yes) cout << Yes << '\n'; else cout << No << '\n'; } template void output_row(std::vector &row) { int N = row.size(); for (int i = 0; i < N; ++i) { if (i > 0) cout << ' '; cout << row.at(i); } cout << '\n'; } template void output_col(std::vector &col) { int N = col.size(); for (int i = 0; i < N; ++i) { cout << col.at(i) << '\n'; } } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }