// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lg = long long; using pii = pair; using pll = pair; #define TEST cerr << "TEST" << endl // #define AMARI 998244353 #define AMARI 1000000007 #define TEMOTO ((sizeof(long double) == 16) ? false : true) #define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000) #define mpr make_pair #define el '\n' #define El '\n' #define MULTI_TEST_CASE false void solve(void) { 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) % 2 == 0) { cout << "No" << el; return; } if(k % 2 != (h + w) % 2) { cout << "No" << el; return; } if((k - (r - l + 1)) - ((h - 1) + (w - 1)) < 0) { cout << "No" << el; return; } vector> oufucu_tate(h, vector(w, false)),oufucu_yoko(h, vector(w, false)),oufucu(h, vector(w, false)); vector> kaiten_00(h,vector(w,false)),kaiten_01(h,vector(w,false)),kaiten_10(h,vector(w,false)),kaiten_11(h,vector(w,false)); vector> kaiten(h,vector(w,false)); for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { if(i != 0 && i != h - 1 && s[i][j] == '.' && s[i - 1][j] == '.' && s[i + 1][j] == '.')oufucu_tate[i][j] = true; if(j != 0 && j != w - 1 && s[i][j] == '.' && s[i][j - 1] == '.' && s[i][j + 1] == '.')oufucu_yoko[i][j] = true; if(oufucu_tate[i][j] || oufucu_yoko[i][j]) oufucu[i][j] = true; if(i != h - 1 && j != w - 1 && s[i][j] == '.' && s[i + 1][j] == '.' && s[i][j + 1] == '.' && s[i + 1][j + 1] == '.'){ kaiten_00[i][j] = true; kaiten_01[i][j + 1] = true; kaiten_10[i + 1][j] = true; kaiten_11[i + 1][j + 1] = true; } if(kaiten_00[i][j] || kaiten_01[i][j] || kaiten_10[i][j] || kaiten_11[i][j])kaiten[i][j] = true; } } // 左上からl-1回の移動で行けるoufucuがtrueの点を探す // secondについて、上から来た:1 下から来た:2 右から3 左から4 vector> dist00(h, vector(w, mpr(INT_MAX / 2, -1))); dist00[0][0] = mpr(0, 0); queue que; que.push(mpr(0, 0)); while(!que.empty()) { int x, y; tie(x, y) = que.front(); que.pop(); if(x != 0 && s[x - 1][y] == '.' && dist00[x - 1][y].first > dist00[x][y].first + 1) { dist00[x - 1][y].first = dist00[x][y].first + 1; dist00[x - 1][y].second = 2; que.push(mpr(x - 1, y)); } if(x != h - 1 && s[x + 1][y] == '.' && dist00[x + 1][y].first > dist00[x][y].first + 1) { dist00[x + 1][y].first = dist00[x][y].first + 1; dist00[x + 1][y].second = 1; que.push(mpr(x + 1, y)); } if(y != 0 && s[x][y - 1] == '.' && dist00[x][y - 1].first > dist00[x][y].first + 1) { dist00[x][y - 1].first = dist00[x][y].first + 1; dist00[x][y - 1].second = 3; que.push(mpr(x, y - 1)); } if(y != w - 1 && s[x][y + 1] == '.' && dist00[x][y + 1].first > dist00[x][y].first + 1) { dist00[x][y + 1].first = dist00[x][y].first + 1; dist00[x][y + 1].second = 4; que.push(mpr(x, y + 1)); } } // 右下からk-r回の移動で行けるoufucuがtrueの点を探す // secondについて、上から来た:1 下から来た:2 右から3 左から4 vector> disthw(h, vector(w, mpr(INT_MAX / 2, -1))); disthw[h - 1][w - 1] = mpr(0, 0); while(!que.empty()) que.pop(); que.push(mpr(h - 1, w - 1)); while(!que.empty()) { int x, y; tie(x, y) = que.front(); que.pop(); if(x != 0 && s[x - 1][y] == '.' && disthw[x - 1][y].first > disthw[x][y].first + 1) { disthw[x - 1][y].first = disthw[x][y].first + 1; disthw[x - 1][y].second = 2; que.push(mpr(x - 1, y)); } if(x != h - 1 && s[x + 1][y] == '.' && disthw[x + 1][y].first > disthw[x][y].first + 1) { disthw[x + 1][y].first = disthw[x][y].first + 1; disthw[x + 1][y].second = 1; que.push(mpr(x + 1, y)); } if(y != 0 && s[x][y - 1] == '.' && disthw[x][y - 1].first > disthw[x][y].first + 1) { disthw[x][y - 1].first = disthw[x][y].first + 1; disthw[x][y - 1].second = 3; que.push(mpr(x, y - 1)); } if(y != w - 1 && s[x][y + 1] == '.' && disthw[x][y + 1].first > disthw[x][y].first + 1) { disthw[x][y + 1].first = disthw[x][y].first + 1; disthw[x][y + 1].second = 4; que.push(mpr(x, y + 1)); } } pii tyuucan = mpr(-1, -1); for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { // if(oufucu[i][j])cerr << i << j << el; if(dist00[i][j].first <= l - 1 && disthw[i][j].first <= k - r && oufucu[i][j] == true) { tyuucan = mpr(i, j); break; } } if(tyuucan.first != -1) break; } // cerr << dist00[1][1].first << ' ' << disthw[1][1].first << el; if(tyuucan.first == -1) { if((r - l + 1) % 4 != 0){ cout << "No" << el; return; } pii siten = mpr(-1,-1); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(dist00[i][j].first <= l - 1 && disthw[i][j].first <= k - r && kaiten[i][j] == true){ siten = mpr(i,j); break; } } if(siten.first != -1)break; } if(siten.first == -1){ //TEST; cout << "No" << el; return; } cout << "Yes" << el; string zenhan, kouhan; pii temp = siten; while(temp.first != 0 || temp.second != 0) { if(dist00[temp.first][temp.second].second == 4) { zenhan.push_back('R'); temp.second--; continue; } if(dist00[temp.first][temp.second].second == 3) { zenhan.push_back('L'); temp.second++; continue; } if(dist00[temp.first][temp.second].second == 2) { zenhan.push_back('U'); temp.first++; continue; } if(dist00[temp.first][temp.second].second == 1) { zenhan.push_back('D'); temp.first--; continue; } } //cerr << siten.first << siten.second << el; for(int i = zenhan.size() - 1; i >= 0; i--) cout << zenhan[i]; //ここで回転の出力をやる if(kaiten_00[siten.first][siten.second]){ int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first; for(int i = 0; i < cnt / 4; i++) cout << "DRUL"; } else if(kaiten_01[siten.first][siten.second]){ int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first; for(int i = 0; i < cnt / 4; i++) cout << "DLUR"; } else if(kaiten_10[siten.first][siten.second]){ int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first; for(int i = 0; i < cnt / 4; i++) cout << "URDL"; } else{ int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first; for(int i = 0; i < cnt / 4; i++) cout << "ULDR"; } temp = siten; // secondについて、上から来た:1 下から来た:2 右から3 左から4 while(temp.first != h - 1 || temp.second != w - 1) { //cerr << temp.first << ' ' << temp.second << el; if(disthw[temp.first][temp.second].second == 4) { kouhan.push_back('L'); temp.second--; continue; } if(disthw[temp.first][temp.second].second == 3) { kouhan.push_back('R'); temp.second++; continue; } if(disthw[temp.first][temp.second].second == 2) { kouhan.push_back('D'); temp.first++; continue; } if(disthw[temp.first][temp.second].second == 1) { kouhan.push_back('U'); temp.first--; continue; } } for(int i = 0; i < kouhan.size(); i++) cout << kouhan[i]; cout << el; return; } cout << "Yes" << el; string zenhan, kouhan; pii temp = tyuucan; // secondについて、上から来た:1 下から来た:2 右から3 左から4 while(temp.first != 0 || temp.second != 0) { if(dist00[temp.first][temp.second].second == 4) { zenhan.push_back('R'); temp.second--; continue; } if(dist00[temp.first][temp.second].second == 3) { zenhan.push_back('L'); temp.second++; continue; } if(dist00[temp.first][temp.second].second == 2) { zenhan.push_back('U'); temp.first++; continue; } if(dist00[temp.first][temp.second].second == 1) { zenhan.push_back('D'); temp.first--; continue; } } for(int i = zenhan.size() - 1; i >= 0; i--) cout << zenhan[i]; if(oufucu_tate[tyuucan.first][tyuucan.second]) { int cnt = k - dist00[tyuucan.first][tyuucan.second].first - disthw[tyuucan.first][tyuucan.second].first; for(int i = 0; i < cnt / 2; i++) cout << "UD"; } else { int cnt = k - dist00[tyuucan.first][tyuucan.second].first - disthw[tyuucan.first][tyuucan.second].first; for(int i = 0; i < cnt / 2; i++) cout << "LR"; } temp = tyuucan; int ccnt = 0; // secondについて、上から来た:1 下から来た:2 右から3 左から4 while(temp.first != h - 1 || temp.second != w - 1) { //cerr << temp.first << ' ' << temp.second << el; if(disthw[temp.first][temp.second].second == 4) { kouhan.push_back('L'); temp.second--; continue; } if(disthw[temp.first][temp.second].second == 3) { kouhan.push_back('R'); temp.second++; continue; } if(disthw[temp.first][temp.second].second == 2) { kouhan.push_back('D'); temp.first++; continue; } if(disthw[temp.first][temp.second].second == 1) { kouhan.push_back('U'); temp.first--; continue; } } for(int i = 0; i < kouhan.size(); i++) cout << kouhan[i]; cout << el; return; } void calc(void) { return; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE) cin >> t; while(t--) { solve(); } return 0; }