結果
| 問題 |
No.2411 Reverse Directions
|
| コンテスト | |
| ユーザー |
 kanzakihikaru
|
| 提出日時 | 2023-08-11 23:36:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,035 bytes |
| コンパイル時間 | 4,498 ms |
| コンパイル使用メモリ | 263,536 KB |
| 最終ジャッジ日時 | 2025-02-16 02:15:31 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 WA * 13 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
#include <string>
#define rep(i, l, r) for(ll i = (l); i <= (r); i++)
#define rrep(i, l, r) for(ll i = (r); i >= (l); i--)
#define ff first
#define ss second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
const int INF32 = 2147483647;
const ll INF64 = 9223372036854775807ll;
const int MAX=5100000;
using namespace std;
using namespace atcoder;
const ll MOD=998244353ll;
using mint = modint998244353;
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
if (a < b) {
a = b; // aをbで更新
return true;
}
return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
if (a > b) {
a = b; // aをbで更新
return true;
}
return false;
}
//cin, cout
void CIN() {};
template <class T, class... U>
void CIN(T &&x, U &&...y) {
cin >> x;
CIN(forward<U>(y)...);
}
void _COUT() { cout << '\n'; }
template <class T, class... U>
void _COUT(T &&x, U &&...y) {
cout << ' ' << x;
_COUT(forward<U>(y)...);
}
void COUT() { _COUT(); };
template <class T, class... U>
void COUT(T &&x, U &&...y) {
cout << x;
_COUT(forward<U>(y)...);
}
vector<long long> fact, fact_inv, inv;
/* init_nCk :二項係数のための前処理
計算量:O(n)
*/
void init_nCk(int SIZE) {
fact.resize(SIZE + 5);
fact_inv.resize(SIZE + 5);
inv.resize(SIZE + 5);
fact[0] = fact[1] = 1;
fact_inv[0] = fact_inv[1] = 1;
inv[1] = 1;
for (int i = 2; i < SIZE + 5; i++) {
fact[i] = fact[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
}
}
/* nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
計算量:O(1)
*/
long long nCk(int n, int k) {
assert(!(n < k));
assert(!(n < 0 || k < 0));
return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}
bool check_grid(ll x, ll y, ll H, ll W){
if(x < 0 || H <= x){return false;}
else if(y < 0 || W <= y){return false;}
return true;
}
int main()
{
cin.tie(0); ios::sync_with_stdio(false);
ll H, W, K, L, R;
cin >> H >> W >> K >> L >> R;
vector<string> S(H+2); rep(i, 1, H){cin >> S.at(i); S[i] = '#' + S[i] + '#';}
rep(i, 1, W+2){S[0].push_back('#'); S[H+1].push_back('#');}
ll dist = (H-1) + (W-1);
ll move = K - (R - L + 1);
if(dist % 2 != K % 2){cout << "No" << endl; return 0;}
if(move < dist){cout << "No" << endl; return 0;}
if((R-L+1) % 2 == 1){cout << "No" << endl; return 0;}
vector<vector<int>> safe(H+2, vector<int>(W+2, -1));
vector<vector<int>> safe2(H+2, vector<int>(W+2, -1));
rep(i, 1, H){rep(j, 1, W){
// 周期2
if(S[i][j] == '.' && S[i-1][j] == '.' && S[i+1][j] == '.'){safe[i][j] = 0;}
if(S[i][j] == '.' && S[i][j-1] == '.' && S[i][j+1] == '.'){safe[i][j] = 1;}
// 周期4
if(S[i][j] == '.' && S[i-1][j-1] == '.' && S[i][j-1] == '.' && S[i-1][j] == '.' && S[i+1][j+1] == '.' && S[i][j+1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 0;}
if(S[i][j] == '.' && S[i-1][j+1] == '.' && S[i][j+1] == '.' && S[i-1][j] == '.' && S[i+1][j-1] == '.' && S[i][j-1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 1;}
//if(S[i][j] == '.' && S[i+1][j-1] == '.' && S[i][j-1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 2;}
//if(S[i][j] == '.' && S[i+1][j+1] == '.' && S[i][j+1] == '.' && S[i+1][j] == '.'){safe2[i][j] = 3;}
}}
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};
string mv = "DURL";
string mv_rev = "UDLR";
string mv2[2] = {"UD", "LR"};
string mv4[4] = {"ULDR", "URDL", "DLUR", "DRUL"};
vector<vector<int>> dist_from(H+2, vector<int>(W+2, -1)); dist_from[1][1] = 0;
deque<pair<int, int>> que; que.push_back({1, 1});
while(!que.empty()){
auto [ni, nj] = que.front(); que.pop_front();
rep(i, 0, 3){
int nxi = ni + di[i]; int nxj = nj + dj[i];
if(S[nxi][nxj] == '#'){continue;}
if(dist_from[nxi][nxj] != -1){continue;}
dist_from[nxi][nxj] = dist_from[ni][nj] + 1;
que.push_back({nxi, nxj});
}
}
vector<vector<int>> dist_to(H+2, vector<int>(W+2, -1)); dist_to[H][W] = 0;
que.push_back({H, W});
while(!que.empty()){
auto [ni, nj] = que.front(); que.pop_front();
rep(i, 0, 3){
int nxi = ni + di[i]; int nxj = nj + dj[i];
if(S[nxi][nxj] == '#'){continue;}
if(dist_to[nxi][nxj] != -1){continue;}
dist_to[nxi][nxj] = dist_to[ni][nj] + 1;
que.push_back({nxi, nxj});
}
}
//rep(i, 1, H){rep(j, 1, W){cout << dist_to[i][j] << " ";} cout << endl;}
rep(i, 1, H){rep(j, 1, W){
ll cnt = K - dist_to[i][j] - dist_from[i][j];
if(safe[i][j] == 0){continue;}
if(dist_from[i][j] == -1){continue;}
if(dist_to[i][j] == -1){continue;}
if(dist_from[i][j] >= L){continue;}
if(dist_to[i][j] < (K - R)){continue;}
if(dist_to[i][j] % 2 != (K - R) % 2){continue;}
int flag = 0;
if(cnt % 4 == 0 && safe2[i][j] != -1){flag = 1;}
if(cnt % 2 == 0 && safe[i][j] != -1){flag = 2;}
if(flag == 0){continue;}
string ans = "";
cout << "Yes" << endl;
int ni = i, nj = j;
for(ll k = dist_from[i][j]; k > 0; k--){
rep(x, 0, 3){
if(dist_from[ni+di[x]][nj+dj[x]] == k-1){
ni = ni+di[x]; nj = nj+dj[x];
ans.push_back(mv_rev[x]); break;
}
}
}
reverse(ALL(ans)); //cout << ans << endl;
if(flag == 1){
rep(k, 1, cnt / 4){ans += mv4[safe2[i][j]];}
}
else{
rep(k, 1, cnt / 2){ans += mv2[safe[i][j]];}
} //cout << ans << endl;
ni = i; nj = j;
for(ll k = dist_to[i][j]; k > 0; k--){
rep(x, 0, 3){
if(dist_to[ni+di[x]][nj+dj[x]] == k-1){
ni = ni+di[x]; nj = nj+dj[x];
ans.push_back(mv[x]); break;
}
}
}
cout << ans << endl; return 0;
}}
cout << "No" << endl;
return 0;
}