結果

問題 No.124 門松列(3)
ユーザー 14番
提出日時 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.

ソースコード

diff #
プレゼンテーションモードにする

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 3
5 4 1
6 6 9
2 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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0