#include using namespace std; typedef long long int ll; typedef unsigned long long ull; typedef long double ld; int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 }; const long long mod = 998244353; const ll inf = 1LL << 60; const int INF = 5e8; struct dsu { public: dsu() : _n(0) { } dsu(int n) : _n(n) , parent_or_size(n, -1) { } int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } // 頂点aの属する連結成分の代表元を返す int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } // 頂点aの属する連結成分のサイズを返す int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } // グラフを連結成分に分け、その情報を返します。 // 返り値は「「一つの連結成分の頂点番号のリスト」のリスト」です。 //(内側外側限らず)vector内でどの順番で頂点が格納されているかは未定義です。 std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; int main() { int h, w, k, l, r; cin >> h >> w >> k >> l >> r; vector s(h); for (int i = 0; i < h; i++) cin >> s[i]; if ((h + w) % 2 != k % 2 or (l - r + 1) % 2 or h - 1 + w - 1 > k) { cout << "No" << endl; return 0; } dsu uf(h * w); vector> ok(h, vector(w)); for (int i = 1; i < h - 1; i++) { for (int j = 1; j < w - 1; j++) { if (s[i][j] == '#') continue; if ((i + 1 < h) and i and s[i + 1][j] == '.' and s[i - 1][j] == '.') ok[i][j] = true; if ((j + 1 < w) and j and s[i][j + 1] == '.' and s[i][j - 1] == '.') ok[i][j] = true; } } for (int i = 0; i < h - 1; i++) { for (int j = 0; j < w - 1; j++) { if (s[i][j] == '#') continue; if ((i + 1 < h) and (j + 1 < w) and s[i][j + 1] == '.' and s[i + 1][j] == '.' and s[i + 1][j + 1] == '.') ok[i][j] = true; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i][j] == '#') continue; if (j + 1 < w and s[i][j + 1] == '.') uf.merge(i * w + j, i * w + j + 1); if (i + 1 < h and s[i + 1][j] == '.') uf.merge(i * w + j, (i + 1) * w + j); } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (ok[i][j] and uf.same(0, i * w + j) and uf.same(i * w + j, h * w - 1)) { string t = ""; auto bfs = [&](int sx, int sy, int gx, int gy) -> string { if (sx == gx and sy == gy) return ""; queue> q; vector> vis(h, vector(w)); vector>> pre(h, vector>(w)); q.emplace(sx, sy); vis[sx][sy] = 1; while (q.size()) { auto [x, y] = q.front(); q.pop(); if (x == gx and y == gy) break; for (int id = 0; id < 4; id++) { int nx = x + dx[id], ny = y + dy[id]; if (nx < 0 or ny < 0 or nx >= h or ny >= w or s[nx][ny] == '#') continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; pre[nx][ny] = { x, y }; q.emplace(nx, ny); } } string ret = ""; int X = gx, Y = gy; while (X != sx or Y != sy) { auto [px, py] = pre[X][Y]; if (px == X) { ret.push_back('R'); } else { ret.push_back('D'); } X = px; Y = py; } reverse(ret.begin(), ret.end()); return ret; }; t += bfs(0, 0, i, j); string t_ = bfs(i, j, h - 1, w - 1); int rest = t_.size(); if ((int)t.size() + rest >= k) continue; if ((k - (int)t.size() - rest) % 2) continue; if (i + 1 < h and i and s[i + 1][j] == '.' and s[i - 1][j] == '.') { while ((int)t.size() < k - rest) { t.push_back('U'); t.push_back('D'); } } else if (j + 1 < w and j and s[i][j + 1] == '.' and s[i][j - 1] == '.') { while ((int)t.size() < k - rest) { t.push_back('R'); t.push_back('L'); } } else { if ((k - (int)t.size() - rest) % 4) continue; while ((int)t.size() < k - rest) { t.push_back('R'); t.push_back('D'); t.push_back('L'); t.push_back('U'); } } t += t_; cout << "Yes" << endl; cout << t << endl; return 0; } } } cout << "No" << endl; }