結果

問題 No.2411 Reverse Directions
ユーザー Carpenters-Cat
提出日時 2023-08-11 23:33:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,794 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 203,340 KB
最終ジャッジ日時 2025-02-16 02:13:39
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 15 WA * 12 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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