結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 kakel-san
|
| 提出日時 | 2023-08-11 22:55:28 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 82 ms / 2,000 ms |
| コード長 | 5,274 bytes |
| コンパイル時間 | 1,156 ms |
| コンパイル使用メモリ | 114,344 KB |
| 実行使用メモリ | 26,752 KB |
| 最終ジャッジ日時 | 2024-11-18 18:07:20 |
| 合計ジャッジ時間 | 3,893 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (h, w, k, l, r) = (c[0], c[1], c[2], c[3], c[4]);var map = SList(h);if ((r - l) % 2 == 0 || l == 1 || r == k){WriteLine("No");return;}var vrev = new bool[h][];for (var i = 0; i < vrev.Length; ++i){vrev[i] = new bool[w];for (var j = 0; j < vrev[i].Length; ++j){if (i > 0 && i + 1 < h && map[i - 1][j] == '.' && map[i][j] == '.' && map[i + 1][j] == '.') vrev[i][j] = true;}}var hrev = new bool[h][];for (var i = 0; i < hrev.Length; ++i){hrev[i] = new bool[w];for (var j = 1; j + 1 < hrev[i].Length; ++j){if (map[i][j - 1] == '.' && map[i][j] == '.' && map[i][j + 1] == '.') hrev[i][j] = true;}}var slen = new int[h][];for (var i = 0; i < slen.Length; ++i) slen[i] = Enumerable.Repeat(int.MaxValue, w).ToArray();slen[0][0] = 0;var q = new Queue<(int x, int y)>();q.Enqueue((0, 0));while (q.Count > 0){var cur = q.Dequeue();for (var i = 0; i < mx.Length; ++i){var nx = cur.x + mx[i];var ny = cur.y + my[i];if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;if (map[nx][ny] != '.') continue;if (slen[nx][ny] <= slen[cur.x][cur.y] + 1) continue;slen[nx][ny] = slen[cur.x][cur.y] + 1;q.Enqueue((nx, ny));}}var tlen = new int[h][];for (var i = 0; i < tlen.Length; ++i) tlen[i] = Enumerable.Repeat(int.MaxValue, w).ToArray();tlen[h - 1][w - 1] = 0;q.Enqueue((h - 1, w - 1));while (q.Count > 0){var cur = q.Dequeue();for (var i = 0; i < mx.Length; ++i){var nx = cur.x + mx[i];var ny = cur.y + my[i];if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;if (map[nx][ny] != '.') continue;if (tlen[nx][ny] <= tlen[cur.x][cur.y] + 1) continue;tlen[nx][ny] = tlen[cur.x][cur.y] + 1;q.Enqueue((nx, ny));}}for (var i = 0; i < h; ++i) for (var j = 0; j < w; ++j){if (slen[i][j] <= l - 1 && (l - 1 - slen[i][j]) % 2 == 0 &&tlen[i][j] <= k - r && (k - r - tlen[i][j]) % 2 == 0 && (vrev[i][j] || hrev[i][j])){var ans = Reverse(Move(0, 0, i, j, slen));while (ans.Count + 1 < l){ans.Add(Rev(ans[ans.Count - 1]));}for (var p = 0; p < r - l + 1; p += 2){if (vrev[i][j]){ans.Add('U');ans.Add('D');}else{ans.Add('L');ans.Add('R');}}ans.AddRange(Move(h - 1, w - 1, i, j, tlen));while (ans.Count < k){ans.Add(Rev(ans[ans.Count - 1]));}WriteLine("Yes");WriteLine(string.Concat(ans));return;}}WriteLine("No");}static int[] mx = new int[] { 0, 0, -1, 1 };static int[] my = new int[] { -1, 1, 0, 0 };static string mc = "LRUD";static List<char> Move(int sx, int sy, int tx, int ty, int[][] len){var cx = tx;var cy = ty;var ans = new List<char>();while (cx != sx || cy != sy){for (var i = 0; i < mx.Length; ++i){var nx = cx + mx[i];var ny = cy + my[i];if (nx < 0 || nx >= len.Length || ny < 0 || ny >= len[nx].Length) continue;if (len[nx][ny] < len[cx][cy]){ans.Add(mc[i]);cx = nx;cy = ny;break;}}}return ans;}static List<char> Reverse(List<char> list){var ans = list.Select(c => Rev(c)).ToList();ans.Reverse();return ans;}static char Rev(char c){if (c == 'L') return 'R';if (c == 'R') return 'L';if (c == 'U') return 'D';return 'U';}}