結果
問題 | No.124 門松列(3) |
ユーザー |
![]() |
提出日時 | 2016-04-17 13:18:42 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 35 ms / 5,000 ms |
コード長 | 4,373 bytes |
コンパイル時間 | 824 ms |
コンパイル使用メモリ | 114,976 KB |
実行使用メモリ | 23,680 KB |
最終ジャッジ日時 | 2024-10-04 10:24:26 |
合計ジャッジ時間 | 2,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
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.Text;using System.Linq;class Program{public void Proc(){Reader.IsDebug = false;int[] inpt = Reader.GetInt();int width = inpt[0];int height = inpt[1];int[,] map = new int[height, width];for(int i=0; i<height; i++) {inpt = Reader.GetInt();for(int j=0; j<width; j++) {map[i,j] = inpt[j];}}Queue<TaskItem> task = new Queue<TaskItem>();task.Enqueue(new TaskItem(0,0,-1,0));task.Enqueue(new TaskItem(0,0,100,0));Dictionary<int, int>[,] step = new Dictionary<int, int>[height, width];while (task.Count > 0){TaskItem t = task.Dequeue();if(step[t.Y, t.X] == null) {step[t.Y, t.X] = new Dictionary<int, int>();}if(step[t.Y, t.X].ContainsKey(t.Prev)) {if(step[t.Y, t.X][t.Prev] <= t.NextStep) {continue;} else {step[t.Y, t.X][t.Prev] = t.NextStep;}} else {step[t.Y, t.X].Add(t.Prev, t.NextStep);}if(t.X == width - 1 && t.Y == height - 1) {continue;}List<int[]> nextPosList = new List<int[]>();if(t.Y > 0) {nextPosList.Add(new int[]{t.Y-1, t.X});}if(t.Y < height - 1) {nextPosList.Add(new int[]{t.Y+1, t.X});}if(t.X > 0) {nextPosList.Add(new int[]{t.Y, t.X - 1});}if(t.X < width - 1) {nextPosList.Add(new int[]{t.Y, t.X + 1});}int nowLen = map[t.Y, t.X];nextPosList.ForEach((a)=>{int nextY = a[0];int nextX = a[1];int nextLen = map[nextY, nextX];if(nowLen == nextLen || t.Prev == nextLen) {return;}if(t.Prev > nowLen && nowLen > nextLen) {return;}if(t.Prev < nowLen && nowLen < nextLen) {return;}TaskItem newTask = new TaskItem(nextX, nextY, nowLen, t.NextStep + 1);task.Enqueue(newTask);});}int ans = 0;if(step[height-1, width-1] == null) {ans = -1;} else {ans = step[height-1, width-1].Values.Min();}Console.WriteLine(ans);}public class TaskItem {public int X;public int Y;public int Prev;public int NextStep;public TaskItem(int x, int y, int prev, int nextstep) {this.X = x;this.Y = y;this.Prev = prev;this.NextStep = nextstep;}}public class CellState {public int Prev;public int Step;public CellState(int prev, int step) {this.Prev = prev;this.Step = step;}}public class Reader{public static bool IsDebug = true;private static String PlainInput = @"3 35 4 16 6 92 8 8";private static System.IO.StringReader Sr = null;public static string ReadLine(){if (IsDebug){if (Sr == null){Sr = new System.IO.StringReader(PlainInput.Trim());}return Sr.ReadLine();}else{return Console.ReadLine();}}public static int[] GetInt(char delimiter = ' ', bool trim = false){string inptStr = ReadLine();if (trim){inptStr = inptStr.Trim();}string[] inpt = inptStr.Split(delimiter);int[] ret = new int[inpt.Length];for (int i = 0; i < inpt.Length; i++){ret[i] = int.Parse(inpt[i]);}return ret;}}static void Main(){Program prg = new Program();prg.Proc();}}