結果

問題 No.2913 二次元距離空間
コンテスト
ユーザー doroneko
提出日時 2025-10-22 02:55:34
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 2,366 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,531 ms
コンパイル使用メモリ 171,104 KB
実行使用メモリ 193,668 KB
最終ジャッジ日時 2025-10-22 02:55:48
合計ジャッジ時間 13,235 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (115 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
raw source code 

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var input = Console.ReadLine().Split();
        int H = int.Parse(input[0]);
        int W = int.Parse(input[1]);

        var grid = new char[H][];
        for (int i = 0; i < H; i++)
            grid[i] = Console.ReadLine().ToCharArray();

        // 移動方向（上、下、左、右）
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, -1, 1 };

        // (左右移動回数, 上下移動回数) の最小値を保存
        var dist = new (int X, int Y)[H, W];
        const int INF = int.MaxValue;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                dist[i, j] = (INF, INF);

        // 優先度付きキュー: (左右移動回数, 上下移動回数, 行, 列)
        var pq = new PriorityQueue<(int X, int Y, int r, int c), (int X, int Y)>();

        dist[0, 0] = (0, 0);
        pq.Enqueue((0, 0, 0, 0), (0, 0));

        while (pq.Count > 0)
        {
            var (x, y, r, c) = pq.Dequeue();
            if ((x, y) != dist[r, c]) continue; // 古い情報はスキップ

            for (int d = 0; d < 4; d++)
            {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                if (grid[nr][nc] == '#') continue;

                int nx = x + (d >= 2 ? 1 : 0); // 左右移動なら X++
                int ny = y + (d < 2 ? 1 : 0);  // 上下移動なら Y++

                var newCost = (nx, ny);
                if (Compare(newCost, dist[nr, nc]) < 0)
                {
                    dist[nr, nc] = newCost;
                    pq.Enqueue((nx, ny, nr, nc), newCost);
                }
            }
        }

        var goal = dist[H - 1, W - 1];
        if (goal.X == INF)
        {
            Console.WriteLine("No");
        }
        else
        {
            Console.WriteLine("Yes");
            Console.WriteLine($"{goal.X} {goal.Y}");
        }
    }

    // (X, Y) の辞書順比較: Xが小さい方が優先。同じならYが小さい方。
    static int Compare((int X, int Y) a, (int X, int Y) b)
    {
        if (a.X != b.X) return a.X < b.X ? -1 : 1;
        if (a.Y != b.Y) return a.Y < b.Y ? -1 : (a.Y > b.Y ? 1 : 0);
        return 0;
    }
}
0