結果
| 問題 |
No.2411 Reverse Directions
|
| コンテスト | |
| ユーザー |
 AngrySadEight
|
| 提出日時 | 2023-07-15 14:19:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 24 ms / 2,000 ms |
| コード長 | 6,624 bytes |
| コンパイル時間 | 1,105 ms |
| コンパイル使用メモリ | 93,576 KB |
| 最終ジャッジ日時 | 2025-02-15 15:00:22 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int, int>;
int main() {
int H, W, K, L, R;
cin >> H >> W >> K >> L >> R;
vector<string> S(H);
for (int i = 0; i < H; i++) {
cin >> S[i];
}
if ((R - L + 1) % 2 == 1) {
cout << "No" << endl;
return 0;
}
if ((H + W - 2) % 2 != K % 2) {
cout << "No" << endl;
return 0;
}
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
vector<char> c = {'D', 'R', 'U', 'L'};
vector<vector<int>> dist_s(H, vector<int>(W, 10000002));
vector<vector<int>> dist_t(H, vector<int>(W, 10000002));
queue<pii> que;
dist_s[0][0] = 0;
que.push(pii(0, 0));
while (que.size()) {
pii p = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
if (p.first + dx[i] >= 0 && p.first + dx[i] < H &&
p.second + dy[i] >= 0 && p.second + dy[i] < W) {
if (S[p.first + dx[i]][p.second + dy[i]] == '#') {
continue;
}
if (dist_s[p.first + dx[i]][p.second + dy[i]] > H * W) {
dist_s[p.first + dx[i]][p.second + dy[i]] =
dist_s[p.first][p.second] + 1;
que.push(pii(p.first + dx[i], p.second + dy[i]));
}
}
}
}
dist_t[H - 1][W - 1] = 0;
que.push(pii(H - 1, W - 1));
while (que.size()) {
pii p = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
if (p.first + dx[i] >= 0 && p.first + dx[i] < H &&
p.second + dy[i] >= 0 && p.second + dy[i] < W) {
if (S[p.first + dx[i]][p.second + dy[i]] == '#') {
continue;
}
if (dist_t[p.first + dx[i]][p.second + dy[i]] > H * W) {
dist_t[p.first + dx[i]][p.second + dy[i]] =
dist_t[p.first][p.second] + 1;
que.push(pii(p.first + dx[i], p.second + dy[i]));
}
}
}
}
/*for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cout << dist_s[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cout << dist_t[i][j] << " ";
}
cout << endl;
}*/
vector<vector<int>> dir(H, vector<int>(W, -1));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (i > 0 && i < H - 1) {
if (S[i][j] == '.' && S[i - 1][j] == '.' &&
S[i + 1][j] == '.') {
dir[i][j] = 1;
}
}
if (j > 0 && j < W - 1) {
if (S[i][j] == '.' && S[i][j - 1] == '.' &&
S[i][j + 1] == '.') {
dir[i][j] = 2;
}
}
}
}
int idx_x = -1;
int idx_y = -1;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (dir[i][j] >= 1) {
if (dist_s[i][j] > L - 1) {
continue;
}
if (abs(dist_s[i][j] - (L - 1)) % 2 == 1) {
continue;
}
if (dist_t[i][j] > K - R) {
continue;
}
if (abs(dist_t[i][j] - (K - R)) % 2 == 1) {
continue;
}
idx_x = i;
idx_y = j;
}
}
}
if (idx_x == -1) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
string ans_str = "";
pii now_idx = pii(idx_x, idx_y);
string ss = "";
while (true) {
if (now_idx.first == 0 && now_idx.second == 0) {
break;
}
for (int i = 0; i < 4; i++) {
if (now_idx.first + dx[i] >= 0 && now_idx.first + dx[i] < H &&
now_idx.second + dy[i] >= 0 && now_idx.second + dy[i] < W) {
if (dist_s[now_idx.first + dx[i]][now_idx.second + dy[i]] ==
dist_s[now_idx.first][now_idx.second] - 1) {
now_idx.first += dx[i];
now_idx.second += dy[i];
ss += c[(i + 2) % 4];
}
}
}
}
while (true) {
if (ss.size() == L - 1) {
break;
}
if (ss[ss.size() - 1] == 'L') {
ss += "RL";
}
if (ss[ss.size() - 1] == 'R') {
ss += "LR";
}
if (ss[ss.size() - 1] == 'U') {
ss += "DU";
}
if (ss[ss.size() - 1] == 'D') {
ss += "UD";
}
}
reverse(ss.begin(), ss.end());
ans_str += ss;
if (dir[idx_x][idx_y] == 1) {
for (int i = 0; i < (R - L + 1) / 2; i++) {
ans_str += "UD";
}
} else {
for (int i = 0; i < (R - L + 1) / 2; i++) {
ans_str += "LR";
}
}
now_idx.first = idx_x;
now_idx.second = idx_y;
string st = "";
while (true) {
if (now_idx.first == H - 1 && now_idx.second == W - 1) {
break;
}
for (int i = 0; i < 4; i++) {
if (now_idx.first + dx[i] >= 0 && now_idx.first + dx[i] < H &&
now_idx.second + dy[i] >= 0 && now_idx.second + dy[i] < W) {
if (dist_t[now_idx.first + dx[i]][now_idx.second + dy[i]] ==
dist_t[now_idx.first][now_idx.second] - 1) {
now_idx.first += dx[i];
now_idx.second += dy[i];
st += c[i];
}
}
}
}
while (true) {
if (st.size() == K - R) {
break;
}
if (st[st.size() - 1] == 'L') {
st += "RL";
}
if (st[st.size() - 1] == 'R') {
st += "LR";
}
if (st[st.size() - 1] == 'U') {
st += "DU";
}
if (st[st.size() - 1] == 'D') {
st += "UD";
}
}
ans_str += st;
cout << ans_str << endl;
}
}