結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 ococonomy1
|
| 提出日時 | 2023-08-11 22:28:07 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,680 bytes |
| コンパイル時間 | 1,594 ms |
| コンパイル使用メモリ | 133,536 KB |
| 実行使用メモリ | 7,936 KB |
| 最終ジャッジ日時 | 2024-04-29 13:29:40 |
| 合計ジャッジ時間 | 4,200 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 7 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 7 ms
7,680 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | AC | 16 ms
7,936 KB |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 2 ms
5,376 KB |
| testcase_14 | AC | 7 ms
5,376 KB |
| testcase_15 | WA | - |
| testcase_16 | AC | 3 ms
5,376 KB |
| testcase_17 | AC | 8 ms
5,376 KB |
| testcase_18 | WA | - |
| testcase_19 | AC | 2 ms
5,376 KB |
| testcase_20 | AC | 6 ms
5,376 KB |
| testcase_21 | AC | 2 ms
5,376 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 2 ms
5,376 KB |
| testcase_24 | WA | - |
| testcase_25 | AC | 2 ms
5,376 KB |
| testcase_26 | AC | 2 ms
5,376 KB |
| testcase_27 | AC | 2 ms
5,376 KB |
| testcase_28 | AC | 12 ms
5,376 KB |
| testcase_29 | AC | 20 ms
6,016 KB |
| testcase_30 | WA | - |
| testcase_31 | AC | 2 ms
5,376 KB |
ソースコード
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using lg = long long;
using pii = pair<int, int>;
using pll = pair<lg, lg>;
#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<string> 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<vector<bool>> oufucu_tate(h, vector<bool>(w, false)),oufucu_yoko(h, vector<bool>(w, false)),oufucu(h, vector<bool>(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;
}
}
// 左上からl-1回の移動で行けるoufucuがtrueの点を探す
// secondについて、上から来た:1 下から来た:2 右から3 左から4
vector<vector<pii>> dist00(h, vector<pii>(w, mpr(INT_MAX / 2, -1)));
dist00[0][0] = mpr(0, 0);
queue<pii> 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<vector<pii>> disthw(h, vector<pii>(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) {
cout << "No" << 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;
}