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

• 問題: No.2411 Reverse Directions
• ユーザー: square1001
• 提出日時: 2023-08-11 21:52:49
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 2,804 bytes
• コンパイル時間: 984 ms
• コンパイル使用メモリ: 88,692 KB
• 最終ジャッジ日時: 2025-02-16 01:17:43
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

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
#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1012345678;
const vector<int> dx = { 0, 1, 0, -1 };
const vector<int> dy = { 1, 0, -1, 0 };
const string ds = "RDLU";
vector<vector<int> > distance(int H, int W, const vector<string>& S, int sx, int sy) {
    vector<vector<int> > dist(H, vector<int>(W, INF));
    dist[sx][sy] = 0;
    queue<int> que;
    que.push(sx * W + sy);
    while (!que.empty()) {
        int cx = que.front() / W;
        int cy = que.front() % W;
        que.pop();
        for (int i = 0; i < 4; i++) {
            int tx = cx + dx[i];
            int ty = cy + dy[i];
            if (0 <= tx && tx < H && 0 <= ty && ty < W && S[tx][ty] == '.' && dist[tx][ty] == INF) {
                dist[tx][ty] = dist[cx][cy] + 1;
                que.push(tx * W + ty);
            }
        }
    }
    return dist;
}
int main() {
    int H, W, K, L, R;
    cin >> H >> W >> K >> L >> R;
    L -= 1;
    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
    }
    if ((R - L) % 2 == 1) {
        cout << "No" << endl;
    }
    else {
        vector<vector<int> > d1 = distance(H, W, S, 0, 0);
        vector<vector<int> > d2 = distance(H, W, S, H - 1, W - 1);
        bool found = false;
        string answer;
        for (int i = 0; i < H && !found; i++) {
            for (int j = 0; j < W && !found; j++) {
                if (d1[i][j] <= L && d1[i][j] % 2 == L % 2 && d2[i][j] <= K - R && d2[i][j] % 2 == (K - R) % 2) {
                    int bit = 0;
                    if (i != 0 && i != H - 1 && S[i - 1][j] == '.' && S[i + 1][j] == '.') {
                        bit |= 1;
                    }
                    if (j != 0 && j != W - 1 && S[i][j - 1] == '.' && S[i][j + 1] == '.') {
                        bit |= 2;
                    }
                    if (bit != 0) {
                        found = true;
                        int ax = i, ay = j;
                        for (int k = 0; k < L; k++) {
                            int best = INF, nx = -1, ny = -1, nd = -1;
                            for (int l = 0; l < 4; l++) {
                                int tx = ax + dx[l], ty = ay + dy[l];
                                if (0 <= tx && tx < H && 0 <= ty && ty < W && best > d1[tx][ty]) {
                                    best = d1[tx][ty];
                                    nx = tx;
                                    ny = ty;
                                    nd = l ^ 2;
                                }
                            }
                            answer += ds[nd];
                            ax = nx;
                            ay = ny;
                        }
                        reverse(answer.begin(), answer.end());
                        for (int i = L; i < R; i++) {
                            answer += (bit & 1 ? (i % 2 == 0 ? 'U' : 'D') : (i % 2 == 0 ? 'L' : 'R'));
                        }
                        int bx = i, by = j;
                        for (int k = R; k < K; k++) {
                            int best = INF, nx = -1, ny = -1, nd = -1;
                            for (int l = 0; l < 4; l++) {
                                int tx = bx + dx[l], ty = by + dy[l];
                                if (0 <= tx && tx < H && 0 <= ty && ty < W && best > d2[tx][ty]) {
                                    best = d2[tx][ty];
                                    nx = tx;
                                    ny = ty;
                                    nd = l;
                                }
                            }
                            answer += ds[nd];
                            bx = nx;
                            by = ny;
                        }
                    }
                }
            }
        }
        if (!found) {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
            cout << answer << endl;
        }
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX