#include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } using P = pair; using T = tuple; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; pair>, vector>> calc_dist(vector s, int sx, int sy){ int h = s.size(), w = s[0].size(); queue

que; auto dist = vec2d(h, w, -1); auto pre = vec2d(h, w, P(-1, -1)); auto set_dist = [&](int i, int j, int d){ if(dist[i][j] == -1){ que.push({i, j}); dist[i][j] = d; return true; } return false; }; auto in_field = [&](int x, int y){ return 0 <= x && x < h && 0 <= y && y < w; }; set_dist(sx, sy, 0); while(!que.empty()){ auto [x, y] = que.front(); que.pop(); for(int k = 0; k < 4; k++) { int xx = x+dx[k]; int yy = y+dy[k]; if(!in_field(xx, yy)) continue; if(s[xx][yy] == '#') continue; if(set_dist(xx, yy, dist[x][y]+1)){ pre[xx][yy] = {x, y}; } } } return make_pair(dist, pre); } string inv(string s){ string ans; for(char c: s){ if(c == 'L') ans += 'R'; if(c == 'R') ans += 'L'; if(c == 'D') ans += 'U'; if(c == 'U') ans += 'D'; } return ans; } string make_path(int x, int y, vector> pre){ string ans; while(true){ auto [xx, yy] = pre[x][y]; if(xx == -1){ assert(yy == -1); break; } if(x == xx+1){ ans += 'D'; }else if(x == xx-1){ ans += 'U'; }else if(y == yy+1){ ans += 'R'; }else{ assert(y == yy-1); ans += 'L'; } x = xx; y = yy; } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int h, w, k, l, r; cin >> h >> w >> k >> l >> r; l--; vector s(h); for(int i = 0; i < h; i++) cin >> s[i]; auto fx = [&](int i, int j){ if(i-1 >= 0 && i+1 < h){ if(s[i-1][j] == '.' && s[i][j] == '.' && s[i+1][j] == '.') return true; } return false; }; auto fy = [&](int i, int j){ if(j-1 >= 0 && j+1 < w){ if(s[i][j-1] == '.' && s[i][j] == '.' && s[i][j+1] == '.') return true; } return false; }; auto f = [&](int i, int j){ return fx(i, j) || fy(i, j); }; if(r%2 != l%2){ cout << "No" << endl; return 0; } if((h+w-2)%2 != (k-(r-l))%2){ cout << "No" << endl; return 0; } if((h+w-2) > k-(r-l)){ cout << "No" << endl; return 0; } auto in_field = [&](int x, int y){ return 0 <= x && x < h && 0 <= y && y < w; }; auto verify = [&](string t){ int x = 0, y = 0; for(char c: t){ if(c == 'D') x++; if(c == 'U') x--; if(c == 'L') y--; if(c == 'R') y++; assert(in_field(x, y)); assert(s[x][y] == '.'); } }; auto [ds, pre_s] = calc_dist(s, 0, 0); auto [dt, pre_t] = calc_dist(s, h-1, w-1); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(ds[i][j] == -1 || dt[i][j] == -1){ continue; } if(!f(i, j)) continue; if((i+j)%2 != l%2) continue; if(ds[i][j] > l) continue; if(dt[i][j] > k-r) continue; int extra = k-(ds[i][j]+dt[i][j]); string ans = make_path(i, j, pre_s); auto ans_inv = ans; // cout << i << ' ' << j << endl; if(fx(i, j)){ while(extra){ ans += "DU"; ans_inv += "UD"; extra-=2; } }else{ assert(fy(i, j)); while(extra){ ans += "LR"; ans_inv += "RL"; extra-=2; } } assert(ans.size() >= r); auto tail = inv(make_path(i, j, pre_t)); ans += tail; ans_inv += tail; cout << "Yes" << endl; cout << ans << endl; assert(ans.size() == k); verify(ans); // verify(ans_inv); return 0; } } cout << "No" << endl; return 0; }