結果

問題 No.1949 足し算するだけのパズルゲーム(2)
コンテスト
ユーザー masayamatu
提出日時 2022-06-18 10:16:00
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 2,043 ms / 3,000 ms
コード長 4,975 bytes
コンパイル時間 11,723 ms
コンパイル使用メモリ 169,652 KB
実行使用メモリ 221,956 KB
最終ジャッジ日時 2024-10-09 21:39:37
合計ジャッジ時間 21,984 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (136 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
//using static CompLib.CompLib;
//using DataStructure;

namespace atcoder
{

    class Program
    {
        const int intMax = 1000000000;
        const long longMax = 2000000000000000000;
        static void Main(string[] args)
        {
            var HWYX = Console.ReadLine().Trim().Split().Select(int.Parse).ToArray();
            int H = HWYX[0];
            int W = HWYX[1];
            int Y = HWYX[2] - 1;
            int X = HWYX[3] - 1;
            var A = new long[H, W];
            for (int i = 0; i < H; i++)
            {
                var read = Console.ReadLine().Trim().Split().Select(int.Parse).ToArray();
                for (int j = 0; j < W; j++)
                {
                    A[i, j] = read[j];
                }
            }
            var pq = new PriorityQueue<Point>(25000000, Comparer<Point>.Create((x, y) => y.CompareTo(x)));
            pq.Push(new Point(Y, X, A[Y, X]));
            var move = new (int, int)[4] { (1, 0), (-1, 0), (0, 1), (0, -1) };
            var visited = new bool[H, W];
            long attack = A[Y, X];
            while (pq.Count > 0)
            {
                Point now = pq.Pop();
                if (now.y != Y || now.x != X)
                {
                    if (attack <= now.cost)
                    {
                        Console.WriteLine("No");
                        return;
                    }
                    else
                    {
                        attack += now.cost;
                    }
                }
                foreach (var i in move)
                {
                    int ny = now.y + i.Item1;
                    int nx = now.x + i.Item2;
                    if (ny >= 0 && ny < H && nx >= 0 && nx < W && !visited[ny, nx])
                    {
                        visited[ny, nx] = true;
                        pq.Push(new Point(ny, nx, A[ny, nx]));
                    }
                }
            }
            Console.WriteLine("Yes");
        }
    }
    public struct Point : IComparable<Point>
        {
            public int y;
            public int x;
            public long cost;
            public Point(int y, int x, long cost)
            {
                this.y = y;
                this.x = x;
                this.cost = cost;
            }
            public int CompareTo(Point other) => cost.CompareTo(other.cost);
        }
        public class PriorityQueue<T> where T : IComparable<T>
    {
        private readonly T[] _array;
        private readonly IComparer _comparer;
        public int Count {get; private set;} = 0;
        public T Root => _array[0];

        public PriorityQueue(int capacity, IComparer comparer = null)
        {
            _array = new T[capacity];
            _comparer = comparer;
        }
        //要素追加
        public void Push(T item)
        {
            _array[this.Count] = item;
            Count += 1;
            var n = Count - 1;
            while(n != 0)
            {
                var parent = (n - 1) / 2;
                if(Compare(_array[n], _array[parent]) > 0)
                {
                    Swap(n, parent);
                    n = parent;
                }
                else
                {
                    break;
                }
            }
        }
        //優先度の一番高いものの取り出し
        public T Pop()
        {
            Swap(0, this.Count - 1);
            Count -= 1;

            var parent = 0;
            while(true)
            {
                var chiled = 2 * parent + 1;
                if(chiled > Count - 1) break;
                if(chiled < Count - 1 && Compare(_array[chiled], _array[chiled + 1]) < 0) chiled += 1;
                if(Compare(_array[parent], _array[chiled]) < 0)
                {
                    Swap(parent, chiled);
                    parent = chiled;
                }
                else
                {
                    break;
                }
            }
            return _array[Count];
        }
        //すべての値を取り出し
        //引数１：True　Pop（）, False　値を取り出だけ
        public IEnumerable<T> GetAllElements(bool withPop = true)
        {
            int count = Count;
            for(int i = 0; i < count; i++)
            {
                if(withPop) yield return Pop();
                else yield return _array[count - i - 1];
            }
        }
        // 引数同士を比較
        private int Compare(T a, T b)
        {
            if(_comparer == null) return a.CompareTo(b);
            return _comparer.Compare(a, b);
        }
        //引数２箇所の入れ替え
        private void Swap(int a, int b)
        {
            var temp = _array[a];
            _array[a] = _array[b];
            _array[b] = temp;
        }
    }
}
0