#include #include #include #include #include #include using namespace std; using pii = pair; 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 ((R - L + 1) % 2 == 1) { cout << "No" << endl; return 0; } if ((H + W - 2) % 2 != K % 2) { cout << "No" << endl; return 0; } vector dx = {1, 0, -1, 0}; vector dy = {0, 1, 0, -1}; vector c = {'D', 'R', 'U', 'L'}; vector> dist_s(H, vector(W, 10000002)); vector> dist_t(H, vector(W, 10000002)); queue que; dist_s[0][0] = 0; que.push(pii(0, 0)); while (que.size()) { pii p = que.front(); que.pop(); for (int i = 0; i < 4; i++) { if (p.first + dx[i] >= 0 && p.first + dx[i] < H && p.second + dy[i] >= 0 && p.second + dy[i] < W) { if (S[p.first + dx[i]][p.second + dy[i]] == '#') { continue; } if (dist_s[p.first + dx[i]][p.second + dy[i]] > H * W) { dist_s[p.first + dx[i]][p.second + dy[i]] = dist_s[p.first][p.second] + 1; que.push(pii(p.first + dx[i], p.second + dy[i])); } } } } dist_t[H - 1][W - 1] = 0; que.push(pii(H - 1, W - 1)); while (que.size()) { pii p = que.front(); que.pop(); for (int i = 0; i < 4; i++) { if (p.first + dx[i] >= 0 && p.first + dx[i] < H && p.second + dy[i] >= 0 && p.second + dy[i] < W) { if (S[p.first + dx[i]][p.second + dy[i]] == '#') { continue; } if (dist_t[p.first + dx[i]][p.second + dy[i]] > H * W) { dist_t[p.first + dx[i]][p.second + dy[i]] = dist_t[p.first][p.second] + 1; que.push(pii(p.first + dx[i], p.second + dy[i])); } } } } /*for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << dist_s[i][j] << " "; } cout << endl; } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << dist_t[i][j] << " "; } cout << endl; }*/ vector> dir(H, vector(W, -1)); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (i > 0 && i < H - 1) { if (S[i][j] == '.' && S[i - 1][j] == '.' && S[i + 1][j] == '.') { dir[i][j] = 1; } } if (j > 0 && j < W - 1) { if (S[i][j] == '.' && S[i][j - 1] == '.' && S[i][j + 1] == '.') { dir[i][j] = 2; } } } } int idx_x = -1; int idx_y = -1; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (dir[i][j] >= 1) { if (dist_s[i][j] > L - 1) { continue; } if (abs(dist_s[i][j] - (L - 1)) % 2 == 1) { continue; } if (dist_t[i][j] > K - R) { continue; } if (abs(dist_t[i][j] - (K - R)) % 2 == 1) { continue; } idx_x = i; idx_y = j; } } } if (idx_x == -1) { cout << "No" << endl; } else { cout << "Yes" << endl; string ans_str = ""; pii now_idx = pii(idx_x, idx_y); string ss = ""; while (true) { if (now_idx.first == 0 && now_idx.second == 0) { break; } for (int i = 0; i < 4; i++) { if (now_idx.first + dx[i] >= 0 && now_idx.first + dx[i] < H && now_idx.second + dy[i] >= 0 && now_idx.second + dy[i] < W) { if (dist_s[now_idx.first + dx[i]][now_idx.second + dy[i]] == dist_s[now_idx.first][now_idx.second] - 1) { now_idx.first += dx[i]; now_idx.second += dy[i]; ss += c[(i + 2) % 4]; } } } } while (true) { if (ss.size() == L - 1) { break; } if (ss[ss.size() - 1] == 'L') { ss += "RL"; } if (ss[ss.size() - 1] == 'R') { ss += "LR"; } if (ss[ss.size() - 1] == 'U') { ss += "DU"; } if (ss[ss.size() - 1] == 'D') { ss += "UD"; } } reverse(ss.begin(), ss.end()); ans_str += ss; if (dir[idx_x][idx_y] == 1) { for (int i = 0; i < (R - L + 1) / 2; i++) { ans_str += "UD"; } } else { for (int i = 0; i < (R - L + 1) / 2; i++) { ans_str += "LR"; } } now_idx.first = idx_x; now_idx.second = idx_y; string st = ""; while (true) { if (now_idx.first == H - 1 && now_idx.second == W - 1) { break; } for (int i = 0; i < 4; i++) { if (now_idx.first + dx[i] >= 0 && now_idx.first + dx[i] < H && now_idx.second + dy[i] >= 0 && now_idx.second + dy[i] < W) { if (dist_t[now_idx.first + dx[i]][now_idx.second + dy[i]] == dist_t[now_idx.first][now_idx.second] - 1) { now_idx.first += dx[i]; now_idx.second += dy[i]; st += c[i]; } } } } while (true) { if (st.size() == K - R) { break; } if (st[st.size() - 1] == 'L') { st += "RL"; } if (st[st.size() - 1] == 'R') { st += "LR"; } if (st[st.size() - 1] == 'U') { st += "DU"; } if (st[st.size() - 1] == 'D') { st += "UD"; } } ans_str += st; cout << ans_str << endl; } }