結果

問題 No.2411 Reverse Directions
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-08-11 23:33:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,794 bytes
コンパイル時間 2,477 ms
コンパイル使用メモリ 211,808 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-18 19:09:02
合計ジャッジ時間 7,334 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 WA -
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
6,816 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 2 ms
6,816 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,816 KB
testcase_20 WA -
testcase_21 AC 2 ms
6,820 KB
testcase_22 RE -
testcase_23 AC 2 ms
6,816 KB
testcase_24 WA -
testcase_25 AC 2 ms
6,816 KB
testcase_26 AC 2 ms
6,816 KB
testcase_27 AC 1 ms
6,816 KB
testcase_28 RE -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int di[] = {0, 1, 0, -1};
int dj[] = {1, 0, -1, 0};
string key = "RDLU";
int main () {
	int N;
	cin >> N;
	int H, W, K, L, R;
	cin >> H >> W >> K >> L >> R;
	L --;
	if ((R - L) & 1) {
		puts("No");
		return 0;
	}
	if ((H + W + K) & 1) {
		puts("No");
		return 0;
	}
	char A[555][555];
	for (int i = 0; i <= H + 1; i ++) {
		for (int j = 0; j <= W + 1; j ++) {
			if (i * j == 0 || i == H + 1 || j == W + 1) {
				A[i][j] = '#';
			} else {
				cin >> A[i][j];
			}
		}
	}
	int D[555][555];
	int C[555][555];
	for (auto& a : D) {
		for (auto& b : a) {
			b = 1e9 + 7;
		}
	}
	D[1][1] = 0;
	queue<pair<int, int>> que;
	que.emplace(1, 1);
	while (!que.empty()) {
		auto [ui, uj] = que.front();
		que.pop();
		for (int i = 0; i < 4; i ++) {
			int vi = ui + di[i], vj = uj + dj[i];
			if (A[vi][vj] == '#') continue;
			if (D[vi][vj] > D[ui][uj] + 1) {
				D[vi][vj] = D[ui][uj] + 1;
				C[vi][vj] = i;
				que.emplace(vi, vj);
			}
		}
	}
	if (D[H][W] > (K - R + L)) {
		puts("No");
		return 0;
	}
	string pt = "";
	int ni = H, nj = W;
	for (int i = 0; i < D[H][W]; i ++) {
		pt += key[C[ni][nj]];
		int p = C[ni][nj];
		ni -= di[p]; nj -= dj[p];
	}
	reverse(pt.begin(), pt.end());
	string ans;
	if (pt.size() < L + 1) {
		int d = C[H][W];
		int b = (d + 2) & 3;
		ans = pt;
		for (int i = 0; i < (K - pt.size()) / 2; i ++) {
			ans += key[b];
			ans += key[d];
		}
	} else {
		ans = pt.substr(0, L + 1);
		int d = 0;
		while (key[d] != ans.back()) d ++;
		int b = (d + 2) & 3;
		ans += key[b];
		while (ans.size() < R) {
			ans += key[d];
			ans += key[b];
		}
		ans += pt.substr(L + 1, pt.size() - (L + 1));
		d = C[H][W];
		b = (d + 2) & 3;
		while (ans.size() < K) {
			ans += key[b];
			ans += key[d];
		}
	}
	puts("Yes");
	cout << ans << endl;
}
0