#ifndef hari64 #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define debug(...) #else #include "util/viewer.hpp" #define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__) #endif // clang-format off using namespace std; using ll = long long; using ld = long double; using pii = pair; using pll = pair; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; using vi = vc; using vl = vc; using vpi = vc; using vpl = vc; #define ALL(x) begin(x), end(x) #define RALL(x) (x).rbegin(), (x).rend() constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001; template bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } // clang-format on int H, W, K, L, R; vector Ss; pii simulateMove(const string& T) { assert(int(T.size()) <= K); int nowX = 0, nowY = 0; for (int i = 0; i < int(T.size()); i++) { if (T[i] == 'U') nowY--; else if (T[i] == 'D') nowY++; else if (T[i] == 'L') nowX--; else if (T[i] == 'R') nowX++; else { assert(false); } if (nowX < 0 || nowX >= W || nowY < 0 || nowY >= H) { return {-1, -1}; } if (Ss[nowY][nowX] == '#') { return {-1, -1}; } assert(Ss[nowY][nowX] == '.'); } return {nowX, nowY}; } bool isValidMovement(const string& T) { assert(int(T.size()) == K); pii res = simulateMove(T); int nowX = res.first, nowY = res.second; if (nowX == -1 && nowY == -1) return false; return nowX == W - 1 && nowY == H - 1; } bool isValidAnswer(const string& T) { if (!isValidMovement(T)) return false; debug(T); string partialyReversed = T; for (int i = L; i <= R; i++) { if (partialyReversed[i] == 'U') partialyReversed[i] = 'D'; else if (partialyReversed[i] == 'D') partialyReversed[i] = 'U'; else if (partialyReversed[i] == 'L') partialyReversed[i] = 'R'; else if (partialyReversed[i] == 'R') partialyReversed[i] = 'L'; else { assert(false); } } debug(partialyReversed); return isValidMovement(partialyReversed); } void fast() { if (L == 0 || R == K - 1) { cout << "No" << endl; } } void slow() { string answer = ""; string path = ""; auto dfs = [&](const auto& f) -> void { if (answer != "") return; if (int(path.size()) == K) { if (isValidAnswer(path)) answer = path; return; } for (char c : {'U', 'D', 'L', 'R'}) { path.push_back(c); if (simulateMove(path) != pii(-1, -1)) { f(f); } path.pop_back(); } }; dfs(dfs); if (answer == "") { cout << "No" << endl; } else { cout << "Yes" << endl; cout << answer << endl; } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W >> K >> L >> R; assert(3 <= H && H <= 500); assert(3 <= W && W <= 500); assert(4 <= K && K <= 500000); assert(1 <= L && L <= R && R <= K); L--; R--; Ss.resize(H); for (int i = 0; i < H; i++) { cin >> Ss[i]; assert(int(Ss[i].size()) == W); for (auto& s : Ss[i]) { assert(s == '.' || s == '#'); } } assert(Ss[0][0] == '.' && Ss[H - 1][W - 1] == '.'); slow(); // fast(); return 0; }