#901148 (C++17) No.2411 Reverse Directions

• 問題: No.2411 Reverse Directions
• ユーザー: kwm_t
• 提出日時: 2023-08-11 23:56:44
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 3,124 bytes
• コンパイル時間: 2,352 ms
• コンパイル使用メモリ: 209,428 KB
• 最終ジャッジ日時: 2025-02-16 02:27:41
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 22 WA * 7

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,-1,0,1 };
char cr[] = { 'U','R','D','L' };
char cr2[] = { 'D','L','U','R' };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w, k, l, r; cin >> h >> w >> k >> l >> r;
    vector<string>s(h);
    rep(i, h)cin >> s[i];
    if (0 == (r - l) % 2) {
        cout << "No" << endl;
        return 0;
    }
    vector<vector<int>> dp(h, vector<int>(w, INF));
    vector<vector<int>> dpR(h, vector<int>(w, INF));
    rep(_, 2) {
        queue<pair<int, int>> q;
        if (0 == _) {
            q.emplace(0, 0);
            dp[0][0] = 0;
        }
        else {
            q.emplace(h - 1, w - 1);
            dp[h - 1][w - 1] = 0;
        }
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            rep(i, 4) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if ((0 <= nx) && (h > nx) && (0 <= ny) && (w > ny) && ('#' != s[nx][ny])) {
                    if (chmin(dp[nx][ny], dp[x][y] + 1)) q.emplace(nx, ny);
                }
            }
        }
        swap(dp, dpR);
    }
    if (0 != abs(dp[h - 1][w - 1] - k) % 2) {
        cout << "No" << endl;
        return 0;
    }
    auto f = [&](int x, int y)->string {
        string ret;
        while (0 != dp[x][y]) {
            rep(i, 4) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0)continue;
                if (ny < 0)continue;
                if (nx >= h)continue;
                if (ny >= w)continue;
                char c = cr[i];
                if (dp[nx][ny] + 1 == dp[x][y]) {
                    x = nx;
                    y = ny;
                    ret += c;
                    break;
                }
            }
        }
        return ret;
    };
    rep(i, h)rep(j, w) {
        if (INF == dp[i][j])continue;
        int he = dp[i][j];
        int ta = dpR[i][j];
        int bo = k - he - ta;
        if (he >= l)continue;
        if (bo < 0)continue;
        if (he + bo < r)continue;
        if ((0 != j) && ('.' == s[i][j - 1]) && (w != j + 1) && ('.' == s[i][j + 1])) {
            string ans0 = f(i, j);
            reverse(all(ans0));
            swap(dp, dpR);
            swap(cr, cr2);
            string ans1;
            rep(i, bo / 2)ans1 += "LR";
            string ans2 = f(i, j);
            cout << "Yes" << endl;
            cout << ans0 + ans1 + ans2 << endl;
            return 0;
        }
        if ((0 != i) && ('.' == s[i - 1][j]) && (h != (i + 1)) && ('.' == s[i + 1][j])) {
            string ans0 = f(i, j);
            reverse(all(ans0));
            swap(dp, dpR);
            swap(cr, cr2);
            string ans1;
            rep(i, bo / 2)ans1 += "DU";
            string ans2 = f(i, j);
            cout << "Yes" << endl;
            cout << ans0 + ans1 + ans2 << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX