結果

問題 No.2411 Reverse Directions
ユーザー 👑 kakel-sankakel-san
提出日時 2023-08-11 22:55:28
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 5,274 bytes
コンパイル時間 1,214 ms
コンパイル使用メモリ 68,448 KB
実行使用メモリ 27,964 KB
最終ジャッジ日時 2023-08-11 22:55:35
合計ジャッジ時間 5,644 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
21,940 KB
testcase_01 AC 61 ms
21,972 KB
testcase_02 AC 61 ms
19,960 KB
testcase_03 AC 60 ms
21,876 KB
testcase_04 AC 78 ms
25,344 KB
testcase_05 AC 62 ms
22,060 KB
testcase_06 AC 67 ms
21,728 KB
testcase_07 AC 71 ms
25,940 KB
testcase_08 AC 60 ms
19,864 KB
testcase_09 AC 60 ms
21,884 KB
testcase_10 AC 104 ms
27,964 KB
testcase_11 AC 66 ms
23,968 KB
testcase_12 AC 107 ms
27,340 KB
testcase_13 AC 62 ms
21,900 KB
testcase_14 AC 80 ms
23,172 KB
testcase_15 AC 73 ms
22,884 KB
testcase_16 AC 64 ms
23,940 KB
testcase_17 AC 83 ms
22,188 KB
testcase_18 AC 72 ms
21,176 KB
testcase_19 AC 59 ms
22,060 KB
testcase_20 AC 75 ms
21,896 KB
testcase_21 AC 71 ms
21,768 KB
testcase_22 AC 91 ms
20,744 KB
testcase_23 AC 60 ms
19,880 KB
testcase_24 AC 104 ms
24,024 KB
testcase_25 AC 62 ms
22,012 KB
testcase_26 AC 65 ms
21,936 KB
testcase_27 AC 70 ms
23,860 KB
testcase_28 AC 98 ms
25,044 KB
testcase_29 AC 116 ms
27,192 KB
testcase_30 AC 102 ms
26,916 KB
testcase_31 AC 90 ms
25,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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';
    }
}
0