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

• 問題: No.2411 Reverse Directions
• ユーザー: Carpenters-Cat
• 提出日時: 2023-08-11 23:33:09
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,794 bytes
• コンパイル時間: 2,356 ms
• コンパイル使用メモリ: 209,856 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-29 14:45:22
• 合計ジャッジ時間: 7,189 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	1 ms; 5,376 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	2 ms; 5,376 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	2 ms; 5,376 KB
testcase_20	WA	-
testcase_21	AC	1 ms; 5,376 KB
testcase_22	RE	-
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	1 ms; 5,376 KB
testcase_28	RE	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	1 ms; 5,376 KB

ソースコード

#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;
}