結果
問題 | No.20 砂漠のオアシス |
ユーザー | 14番 |
提出日時 | 2016-04-02 22:58:41 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 263 ms / 5,000 ms |
コード長 | 4,416 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 113,376 KB |
実行使用メモリ | 29,440 KB |
最終ジャッジ日時 | 2024-10-13 05:36:33 |
合計ジャッジ時間 | 2,793 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
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; class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.GetInt(' ', true); int mapLength = inpt[0]; int maxTairyoku = inpt[1]; int oasisX = inpt[2] - 1; int oasisY = inpt[3] - 1; int[,] map = new int[mapLength, mapLength]; CellState[,] step = new CellState[mapLength, mapLength]; for (int i = 0; i < mapLength; i++) { inpt = Reader.GetInt(' ', true); for (int j = 0; j < mapLength; j++) { map[i, j] = inpt[j]; } } step[0, 0] = new CellState(); step[0, 0].StepNotUseOasis = maxTairyoku; Queue<int[]> task = new Queue<int[]>(); task.Enqueue(new int[] { 0, 0, 0 }); while (task.Count > 0) { int[] pos = task.Dequeue(); int x = pos[0]; int y = pos[1]; bool IsUsedOasis = pos[2] > 0; List<int[]> nextPos = new List<int[]>(); if (x > 0) { nextPos.Add(new int[] { x - 1, y }); } if (x < mapLength - 1) { nextPos.Add(new int[] { x + 1, y }); } if (y > 0) { nextPos.Add(new int[] { x, y - 1 }); } if (y < mapLength - 1) { nextPos.Add(new int[] { x, y + 1 }); } int nowHP = IsUsedOasis?step[y, x].StepUseOasis:step[y,x].StepNotUseOasis; foreach (int[] nextP in nextPos) { int nextX = nextP[0]; int nextY = nextP[1]; if (map[nextY, nextX] < nowHP) { int nextHp = nowHP - map[nextY, nextX]; if (nextX == oasisX && nextY == oasisY && IsUsedOasis == false) { IsUsedOasis = true; nextHp *= 2; } if (step[nextY, nextX] == null || nextHp > (IsUsedOasis?step[nextY, nextX].StepUseOasis:step[nextY, nextX].StepNotUseOasis)) { if(step[nextY, nextX] == null) { CellState cs = new CellState(); step[nextY, nextX] = cs; } if(IsUsedOasis) { step[nextY, nextX].StepUseOasis = nextHp; } else { step[nextY, nextX].StepNotUseOasis = nextHp; } task.Enqueue(new int[] { nextX, nextY, IsUsedOasis ? 1 : 0 }); } } } } if (step[mapLength -1,mapLength-1] != null && Math.Max(step[mapLength - 1, mapLength - 1].StepNotUseOasis, step[mapLength - 1, mapLength-1].StepUseOasis) > 0) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } public class CellState { public int StepUseOasis = 0; public int StepNotUseOasis = 0; } public class Reader { public static bool IsDebug = true; private static String PlainInput = @" "; 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(); } }