結果
問題 | No.124 門松列(3) |
ユーザー | eitaho |
提出日時 | 2015-01-12 00:11:31 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 83 ms / 5,000 ms |
コード長 | 4,024 bytes |
コンパイル時間 | 2,358 ms |
コンパイル使用メモリ | 111,668 KB |
実行使用メモリ | 25,712 KB |
最終ジャッジ日時 | 2023-09-04 04:39:05 |
合計ジャッジ時間 | 5,662 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
21,804 KB |
testcase_01 | AC | 69 ms
23,784 KB |
testcase_02 | AC | 68 ms
21,736 KB |
testcase_03 | AC | 83 ms
25,712 KB |
testcase_04 | AC | 78 ms
21,696 KB |
testcase_05 | AC | 77 ms
23,692 KB |
testcase_06 | AC | 68 ms
21,764 KB |
testcase_07 | AC | 67 ms
19,720 KB |
testcase_08 | AC | 68 ms
21,872 KB |
testcase_09 | AC | 67 ms
21,760 KB |
testcase_10 | AC | 68 ms
23,720 KB |
testcase_11 | AC | 69 ms
21,836 KB |
testcase_12 | AC | 68 ms
23,816 KB |
testcase_13 | AC | 69 ms
23,736 KB |
testcase_14 | AC | 69 ms
21,784 KB |
testcase_15 | AC | 68 ms
21,784 KB |
testcase_16 | AC | 70 ms
21,736 KB |
testcase_17 | AC | 69 ms
21,688 KB |
testcase_18 | AC | 69 ms
21,884 KB |
testcase_19 | AC | 67 ms
21,692 KB |
testcase_20 | AC | 69 ms
19,680 KB |
testcase_21 | AC | 69 ms
23,816 KB |
testcase_22 | AC | 69 ms
19,640 KB |
testcase_23 | AC | 73 ms
21,832 KB |
testcase_24 | AC | 73 ms
19,776 KB |
testcase_25 | AC | 72 ms
21,736 KB |
testcase_26 | AC | 70 ms
21,792 KB |
testcase_27 | AC | 67 ms
23,708 KB |
testcase_28 | AC | 74 ms
23,704 KB |
testcase_29 | AC | 78 ms
21,788 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Text; using System.Linq; using System.Diagnostics; using System.Collections.Generic; using Enu = System.Linq.Enumerable; class Program { static readonly int[] dr = { 0, 0, -1, 1 }; static readonly int[] dc = { -1, 1, 0, 0 }; static readonly int INF = (int)1e9; int H, W; void Solve() { W = reader.Int(); H = reader.Int(); var grid = reader.IntGrid(H); var que = new Queue<State>(); var minCost = new int[H, W, 10]; Fill(minCost, INF); minCost[0, 0, 0] = 0; que.Enqueue(new State(-1, grid[0][0], 0, 0, 0)); while (que.Count > 0) { var s = que.Dequeue(); if (s.r == H - 1 && s.c == W - 1) { Console.WriteLine(s.steps); return; } for (int d = 0; d < dr.Length; d++) { int nr = s.r + dr[d], nc = s.c + dc[d]; if (OK(s, nr, nc, grid)) { if (s.steps + 1 < minCost[nr, nc, s.curr]) { minCost[nr, nc, s.curr] = s.steps + 1; que.Enqueue(new State(s.curr, grid[nr][nc], nr, nc, s.steps + 1)); } } } } Console.WriteLine(-1); } private bool OK(State s, int nr, int nc, int[][] grid) { if (!IsInside(nr, nc)) return false; int next = grid[nr][nc]; if (s.prev == next || s.curr == next) return false; if (s.prev < 0) return true; int mid = new[] { s.prev, s.curr, next }.OrderBy(e => e).ElementAt(1); return mid == s.prev || mid == next; } bool IsInside(int r, int c) { return r >= 0 && r < H && c >= 0 && c < W; } struct State { public short prev, curr, r, c; public int steps; public State(int p2, int p1, int r, int c, int step) { prev = (short)p2; curr = (short)p1; this.r = (short)r; this.c = (short)c; steps = step; } } void Fill<T>(T[, ,] a, T val) { for (int i = 0; i < a.GetLength(0); i++) for (int j = 0; j < a.GetLength(1); j++) for (int k = 0; k < a.GetLength(2); k++) a[i, j, k] = val; } static void Main() { new Program().Solve(); } Reader reader = new Reader(Console.In); class Reader { private readonly TextReader reader; private readonly char[] separator = { ' ' }; private readonly StringSplitOptions removeOp = StringSplitOptions.RemoveEmptyEntries; private string[] A = new string[0]; private int i; public Reader(TextReader r) { reader = r; } public bool HasNext() { return Enqueue(); } public string String() { return Dequeue(); } public int Int() { return int.Parse(Dequeue()); } public long Long() { return long.Parse(Dequeue()); } public double Double() { return double.Parse(Dequeue()); } public int[] IntLine() { var s = Line(); return s == "" ? new int[0] : Array.ConvertAll(Split(s), int.Parse); } public int[] IntArray(int N) { return Enumerable.Range(0, N).Select(i => Int()).ToArray(); } public int[][] IntGrid(int H) { return Enumerable.Range(0, H).Select(i => IntLine()).ToArray(); } public string[] StringArray(int N) { return Enumerable.Range(0, N).Select(i => Line()).ToArray(); } public string Line() { return reader.ReadLine().Trim(); } private string[] Split(string s) { return s.Split(separator, removeOp); } private bool Enqueue() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return Enqueue(); A = Split(line); i = 0; return true; } private string Dequeue() { Enqueue(); return A[i++]; } } }