結果
問題 | No.20 砂漠のオアシス |
ユーザー | sekiya9311 |
提出日時 | 2017-10-14 22:05:04 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 11,413 bytes |
コンパイル時間 | 987 ms |
コンパイル使用メモリ | 112,000 KB |
実行使用メモリ | 23,808 KB |
最終ジャッジ日時 | 2024-11-17 14:52:40 |
合計ジャッジ時間 | 2,658 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
18,048 KB |
testcase_01 | WA | - |
testcase_02 | AC | 28 ms
18,304 KB |
testcase_03 | AC | 29 ms
18,816 KB |
testcase_04 | AC | 31 ms
18,560 KB |
testcase_05 | AC | 73 ms
22,784 KB |
testcase_06 | AC | 93 ms
23,680 KB |
testcase_07 | WA | - |
testcase_08 | AC | 83 ms
23,552 KB |
testcase_09 | AC | 101 ms
23,808 KB |
testcase_10 | AC | 27 ms
18,048 KB |
testcase_11 | WA | - |
testcase_12 | AC | 31 ms
18,688 KB |
testcase_13 | AC | 32 ms
19,072 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 39 ms
20,480 KB |
testcase_18 | WA | - |
testcase_19 | AC | 43 ms
22,144 KB |
testcase_20 | WA | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ProgrammingContest { class MainClass : IDisposable { Scanner sc; Writer wr; string backPath = ".."; char dirSep = System.IO.Path.DirectorySeparatorChar; string inFilePath = null; string outFilePath = null; public MainClass() { this.inFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "in.txt"; this.outFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "out.txt"; } static void Main(string[] args) { using (var mainClass = new MainClass()) { //mainClass.MakeTestCase(); mainClass.Solve(); } } public void Dispose() { if (this.sc != null) { this.sc.Dispose(); this.sc = null; } if (this.wr != null) { this.wr.Dispose(); this.wr = null; } } void MakeTestCase() { Random rand = new Random(); var res = new StringBuilder(); using (var writer = new System.IO.StreamWriter(inFilePath)) writer.Write(res.ToString()); } void Solve() { this.wr = new Writer(this.isReactive); //this.wr = new Writer(this.outFilePath); #if DEBUG if (!this.isReactive) this.sc = new Scanner(this.inFilePath); else this.sc = new Scanner(); #else this.sc = new Scanner(); #endif N = sc.NextInt; V = sc.NextInt; oasis = new Point { y = sc.NextInt - 1, x = sc.NextInt - 1 }; L = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { L[i, j] = sc.NextInt; } } var st = new Point() { x = 0, y = 0 }; var ed = new Point() { x = N - 1, y = N - 1 }; string ans = "NO"; if (Dijkstra(st, ed) < V) { ans = "YES"; } else if (!oasis.Equals(new Point() { x = -1, y = -1 })) { int f = Dijkstra(st, oasis); if (f < V) { int ff = Dijkstra(oasis, ed); if (ff < (V - f) * 2) { ans = "YES"; } } } wr.WriteLine(ans); } int Dijkstra(Point st, Point ed) { var heap = new SkewHeap<State>(); heap.Push(new State()); bool[,] u = new bool[N, N]; u[st.y, st.x] = true; while (!heap.IsEmpty()) { var state = heap.Poll(); var nextPoint = state.p.Next(); foreach (var p in nextPoint) { if (Inside(p)) { if (!u[p.y, p.x]) { int nextCost = state.Cost + L[p.y, p.x]; u[p.y, p.x] = true; if (p.Equals(ed)) { return nextCost; } heap.Push(new State(p, nextCost)); } } } } return -1; } int N, V; Point oasis; int[,] L; bool Inside(Point p) { return 0 <= p.x && p.x < N && 0 <= p.y && p.y < N; } struct State : IComparable<State> { public Point p; public int Cost; public State(int nx, int ny) { p = new Point { x = nx, y = ny }; Cost = 0; } public State(Point p, int cost = 0) { this.p = p; this.Cost = cost; } public int CompareTo(State other) { return Math.Sign(this.Cost - other.Cost); } } struct Point { public int x, y; static Point[] dPoint = new Point[] { new Point{ x = 0, y = -1}, new Point{ x = -1, y = 0}, new Point{ x = 0, y = 1}, new Point{ x = 1, y = 0}, }; private Point Next(Point d) { return new Point { x = this.x + d.x, y = this.y + d.y }; } public List<Point> Next() { List<Point> ret = new List<Point>(); foreach (var el in dPoint) { ret.Add(this.Next(el)); } return ret; } public override bool Equals(object other) { return (other is Point) && ((Point)other).x == this.x && ((Point)other).y == this.y; } } bool isReactive = false; // TODO: reactive check !! } class SkewHeap<T> where T : IComparable<T> { private class HeapNode { public HeapNode l, r; public T val; public static Func<T, T, int> CompareTo; public HeapNode(T val) { this.val = val; l = r = null; } public static HeapNode Meld(HeapNode leftNode, HeapNode rightNode) { if (leftNode == null) { return rightNode; } if (rightNode == null) { return leftNode; } if (HeapNode.CompareTo(leftNode.val, rightNode.val) > 0) { var t = rightNode; rightNode = leftNode; leftNode = t; } leftNode.r = Meld(leftNode.r, rightNode); var t2 = leftNode.l; leftNode.l = leftNode.r; leftNode.r = t2; return leftNode; } } private HeapNode topNode; private int count_; public int Count { get { return this.count_; } } public SkewHeap(Func<T, T, int> comp = null) { HeapNode.CompareTo = (comp ?? ((T l, T r) => l.CompareTo(r))); this.topNode = null; this.count_ = 0; } public void Pop() { this.topNode = HeapNode.Meld(this.topNode.l, this.topNode.r); this.count_--; } public T Top() { return this.topNode.val; } public void Push(T val) { this.topNode = HeapNode.Meld(this.topNode, new HeapNode(val)); this.count_++; } public T Poll() { T retVal = this.Top(); this.Pop(); return retVal; } public bool IsEmpty() { return this.topNode == null; } public void Merge(SkewHeap<T> otherHeap) { this.count_ += otherHeap.Count; this.topNode = HeapNode.Meld(this.topNode, otherHeap.topNode); } } class Writer : IDisposable { System.IO.TextWriter writer; StringBuilder sb; bool isReactive; public Writer(string path) : this(new System.IO.StreamWriter(path)) { } public Writer(bool isReactive) : this(null, isReactive) { } public Writer(System.IO.TextWriter writer = null, bool isReactive = false) { this.writer = (writer ?? Console.Out); if (!(this.isReactive = isReactive)) { this.sb = new StringBuilder(); } } public void Dispose() { if (!isReactive) this.writer.Write(sb.ToString()); if (!this.writer.Equals(Console.Out)) this.writer.Dispose(); } public void Write(object val) { if (this.isReactive) { this.writer.Write(val.ToString()); this.writer.Flush(); } else this.sb.Append(val.ToString()); } public void Write(string format, params object[] vals) { if (this.isReactive) { this.writer.Write(format, vals); this.writer.Flush(); } else this.sb.AppendFormat(format, vals); } public void WriteLine(object val) { this.Write(val.ToString() + System.Environment.NewLine); } public void WriteLine(string format, params object[] vals) { this.Write(format + System.Environment.NewLine, vals); } } class Scanner : IDisposable { Queue<string> buffer; char[] sep; System.IO.TextReader reader; public Scanner(string path) : this(new System.IO.StreamReader(path)) { } public Scanner(System.IO.TextReader reader = null) { this.buffer = new Queue<string>(); this.sep = new char[] { ' ' }; this.reader = (reader ?? Console.In); } private void CheckBuffer() { if (this.buffer.Count == 0) { string str = null; while (string.IsNullOrEmpty(str)) { str = this.reader.ReadLine(); } string[] sreArray = str.Split(this.sep); foreach (string elStr in sreArray) { this.buffer.Enqueue(elStr); } } } public void Dispose() { if (!this.reader.Equals(Console.In)) this.reader.Dispose(); } public string Next { get { this.CheckBuffer(); return this.buffer.Dequeue(); } } public int NextInt { get { return int.Parse(this.Next); } } public double NextDouble { get { return double.Parse(this.Next); } } public long NextLong { get { return long.Parse(this.Next); } } public bool IsEmpty { get { this.CheckBuffer(); return this.buffer.Count == 0; } } } }