結果

問題 No.2731 Two Colors
ユーザー kakel-san
提出日時 2024-04-29 22:04:15
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,031 ms / 3,000 ms
コード長 4,699 bytes
コンパイル時間 14,717 ms
コンパイル使用メモリ 171,448 KB
実行使用メモリ 191,860 KB
最終ジャッジ日時 2024-11-19 06:30:51
合計ジャッジ時間 27,428 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (101 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 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 int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (h, w) = (c[0], c[1]);
var a = NArr(h);
var colors = new int[h][];
for (var i = 0; i < h; ++i) colors[i] = Enumerable.Repeat(-1, w).ToArray();
colors[0][0] = 1;
colors[h - 1][w - 1] = 0;
var ones = new PriorityQueue<Pair>(h, false);
ones.Enqueue(new Pair(0, 1, a[0][1]));
ones.Enqueue(new Pair(1, 0, a[1][0]));
var zeros = new PriorityQueue<Pair>(h, false);
zeros.Enqueue(new Pair(h - 1, w - 2, a[h - 1][w - 2]));
zeros.Enqueue(new Pair(h - 2, w - 1, a[h - 2][w - 1]));
var ans = 0;
var mx = new int[] { 0, 0, -1, 1 };
var my = new int[] { -1, 1, 0, 0 };
while (true)
{
++ans;
var cur = ones.Dequeue();
while (colors[cur.X][cur.Y] >= 0) cur = ones.Dequeue();
colors[cur.X][cur.Y] = 1;
var flg = true;
for (var i = 0; i < 4; ++i)
{
var nx = cur.X + mx[i];
var ny = cur.Y + my[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
if (colors[nx][ny] == 0)
{
flg = false;
break;
}
if (colors[nx][ny] < 0) ones.Enqueue(new Pair(nx, ny, a[nx][ny]));
}
if (!flg) break;
++ans;
cur = zeros.Dequeue();
while (colors[cur.X][cur.Y] >= 0) cur = zeros.Dequeue();
colors[cur.X][cur.Y] = 0;
flg = true;
for (var i = 0; i < 4; ++i)
{
var nx = cur.X + mx[i];
var ny = cur.Y + my[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
if (colors[nx][ny] == 1)
{
flg = false;
break;
}
if (colors[nx][ny] < 0) zeros.Enqueue(new Pair(nx, ny, a[nx][ny]));
}
if (!flg) break;
}
WriteLine(ans);
}
class Pair : IComparable<Pair>
{
public int X;
public int Y;
public int Val;
public Pair(int x, int y, int val)
{
X = x; Y = y; Val = val;
}
public int CompareTo(Pair b)
{
return Val.CompareTo(b.Val);
}
}
class PriorityQueue<T> where T : IComparable<T>
{
public T[] List;
public int Count;
bool IsTopMax;
public PriorityQueue(int count, bool isTopMax)
{
IsTopMax = isTopMax;
List = new T[Math.Max(128, count)];
}
public void Enqueue(T value)
{
if (Count == List.Length)
{
var newlist = new T[List.Length * 2];
for (var i = 0; i < List.Length; ++i) newlist[i] = List[i];
List = newlist;
}
var pos = Count;
List[pos] = value;
++Count;
while (pos > 0)
{
var parent = (pos - 1) / 2;
if (Calc(List[parent], List[pos], true)) break;
Swap(parent, pos);
pos = parent;
}
}
public T Dequeue()
{
--Count;
Swap(0, Count);
var pos = 0;
while (true)
{
var child = pos * 2 + 1;
if (child >= Count) break;
if (child + 1 < Count && Calc(List[child + 1], List[child], false)) ++child;
if (Calc(List[pos], List[child], true)) break;
Swap(pos, child);
pos = child;
}
return List[Count];
}
bool Calc(T a, T b, bool equalVal)
{
var ret = a.CompareTo(b);
if (ret == 0 && equalVal) return true;
return IsTopMax ? ret > 0 : ret < 0;
}
void Swap(int a, int b)
{
var tmp = List[a];
List[a] = List[b];
List[b] = tmp;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0