#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 vll = vc; using vpii = vc; using vpll = vc; using vvi = vc; using vvll = vc; using vvpi = vc; using vvpll = 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 #include struct Timer { void start() { _start = chrono::system_clock::now(); } void stop() { _end = chrono::system_clock::now(); sum += chrono::duration_cast(_end - _start).count(); } inline int ms() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } string report() { return to_string(sum / 1000000) + "[ms]"; } void reset() { _start = chrono::system_clock::now(); sum = 0; } private: chrono::system_clock::time_point _start, _end; long long sum = 0; } timer; 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 slow() { string answer = ""; string path = ""; timer.start(); auto dfs = [&](const auto& f) -> void { if (answer != "") return; if (timer.ms() >= 1800) { assert(false); 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; } } constexpr int DH[4] = {-1, 1, 0, 0}; constexpr int DW[4] = {0, 0, -1, 1}; vvi bfs_dist(int sh, int sw) { vvi dist(H, vi(W, -1)); queue q; dist[sh][sw] = 0; q.push({sh, sw}); while (!q.empty()) { pii v = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nh = v.first + DH[d]; int nw = v.second + DW[d]; if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if (dist[nh][nw] != -1) continue; if (Ss[nh][nw] == '#') continue; dist[nh][nw] = dist[v.first][v.second] + 1; q.push({nh, nw}); } } return dist; } string findPath(int sh, int sw, int gh, int gw) { vvi dist(H, vi(W, INF)); vvc prev(H, vc(W, 'X')); queue q; assert(Ss[sh][sw] == '.'); dist[sh][sw] = 0; q.push({sh, sw}); while (!q.empty() && dist[gh][gw] == INF) { pii v = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nh = v.first + DH[d]; int nw = v.second + DW[d]; if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if (dist[nh][nw] != INF) continue; if (Ss[nh][nw] == '#') continue; dist[nh][nw] = dist[v.first][v.second] + 1; prev[nh][nw] = "UDLR"[d]; q.push({nh, nw}); } } assert(dist[gh][gw] != INF); int nowH = gh; int nowW = gw; string path = ""; while (prev[nowH][nowW] != 'X') { char p = prev[nowH][nowW]; path.push_back(p); if (p == 'U') nowH++; else if (p == 'D') nowH--; else if (p == 'L') nowW++; else if (p == 'R') nowW--; else assert(false); }; reverse(path.begin(), path.end()); return path; } void fast() { if (L == 0 || R == K - 1) { cout << "No" << endl; } if ((R - L + 1) % 2 == 1) { cout << "No" << endl; } vvi distFromStart = bfs_dist(0, 0); vvi distFromGoal = bfs_dist(H - 1, W - 1); for (int h = 0; h < H; h++) { for (int w = 0; w < W; w++) { if (Ss[h][w] == '#') continue; if (distFromStart[h][w] == -1) continue; if (distFromStart[h][w] >= L) continue; if (distFromGoal[h][w] == -1) continue; if (distFromGoal[h][w] > K - R) continue; if (!(distFromStart[h][w] + distFromGoal[h][w] <= K && (K - (distFromStart[h][w] + distFromGoal[h][w])) % 2 == 0)) { continue; } for (int d = 0; d < 4; d++) { int nh = h + DH[d]; int nw = w + DW[d]; if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if (Ss[nh][nw] == '#') continue; { cout << "Yes" << endl; string path1 = findPath(0, 0, h, w); string path3 = findPath(h, w, H - 1, W - 1); string path2 = ""; for (int _ = 0; _ < (K - (distFromStart[h][w] + distFromGoal[h][w])) / 2; _++) { path2.push_back("UDLR"[d]); path2.push_back("DURL"[d]); } string answer = path1 + path2 + path3; assert(isValidAnswer(answer)); cout << answer << endl; return; } } } } cout << "No" << endl; return; } 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; }