結果

問題 No.340 雪の足跡
ユーザー pekempeypekempey
提出日時 2016-01-29 23:56:58
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 633 ms / 1,000 ms
コード長 2,660 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 107,520 KB
実行使用メモリ 50,740 KB
最終ジャッジ日時 2024-09-21 18:51:26
合計ジャッジ時間 11,123 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
30,336 KB
testcase_01 AC 72 ms
30,464 KB
testcase_02 AC 68 ms
29,824 KB
testcase_03 AC 74 ms
30,464 KB
testcase_04 AC 79 ms
30,336 KB
testcase_05 AC 72 ms
29,824 KB
testcase_06 AC 75 ms
30,336 KB
testcase_07 AC 76 ms
30,336 KB
testcase_08 AC 75 ms
30,336 KB
testcase_09 AC 75 ms
30,336 KB
testcase_10 AC 77 ms
30,336 KB
testcase_11 AC 79 ms
31,232 KB
testcase_12 AC 77 ms
30,720 KB
testcase_13 AC 81 ms
30,976 KB
testcase_14 AC 107 ms
34,816 KB
testcase_15 AC 107 ms
35,200 KB
testcase_16 AC 103 ms
35,328 KB
testcase_17 AC 114 ms
35,072 KB
testcase_18 AC 108 ms
34,944 KB
testcase_19 AC 112 ms
35,200 KB
testcase_20 AC 457 ms
42,284 KB
testcase_21 AC 359 ms
44,176 KB
testcase_22 AC 73 ms
29,824 KB
testcase_23 AC 526 ms
49,876 KB
testcase_24 AC 427 ms
50,740 KB
testcase_25 AC 467 ms
45,652 KB
testcase_26 AC 150 ms
36,028 KB
testcase_27 AC 90 ms
33,408 KB
testcase_28 AC 139 ms
41,088 KB
testcase_29 AC 531 ms
50,592 KB
testcase_30 AC 345 ms
38,080 KB
testcase_31 AC 539 ms
49,592 KB
testcase_32 AC 633 ms
50,468 KB
testcase_33 AC 474 ms
40,720 KB
testcase_34 AC 632 ms
50,576 KB
testcase_35 AC 545 ms
48,912 KB
testcase_36 AC 547 ms
49,148 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Contest
{
	class Program
	{
		static void Main(string[] args)
		{
			new Program().Solve();
		}

		void Solve()
		{
			string[] temp = Console.ReadLine().Split();
			int w = int.Parse(temp[0]);
			int h = int.Parse(temp[1]);
			int n = int.Parse(temp[2]);

			int[,] imos = new int[1010, 1010];
			int[,] imos2 = new int[1010, 1010];

			for (int i = 0; i < n; i++)
			{
				int m = int.Parse(Console.ReadLine()) + 1;
				int[] ys = new int[m];
				int[] xs = new int[m];
				int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray();
				for (int j = 0; j < m; j++)
				{
					ys[j] = b[j] / w;
					xs[j] = b[j] % w;
				}
				for (int j = 0; j < m - 1; j++)
				{
					int y1 = Math.Min(ys[j], ys[j + 1]);
					int x1 = Math.Min(xs[j], xs[j + 1]);
					int y2 = Math.Max(ys[j], ys[j + 1]);
					int x2 = Math.Max(xs[j], xs[j + 1]);
					if (y1 == y2)
					{
						imos[y1, x1]++;
						imos[y1, x2]--;
						imos[y2 + 1, x1]--;
						imos[y2 + 1, x2]++;
					}
					else
					{
						imos2[y1, x1]++;
						imos2[y1, x2 + 1]--;
						imos2[y2, x1]--;
						imos2[y2, x2 + 1]++;
					}
				}
			}

			for (int i = 0; i < 1009; i++)
			{
				for (int j = 0; j < 1009; j++)
				{
					imos[i, j + 1] += imos[i, j];
					imos2[i, j + 1] += imos2[i, j];
				}	
			}
			for (int j = 0; j < 1009; j++)
			{
				for (int i = 0; i < 1009; i++)
				{
					imos[i + 1, j] += imos[i, j];
					imos2[i + 1, j] += imos2[i, j];
				}	
			}

			Queue<int> qy = new Queue<int>();
			Queue<int> qx = new Queue<int>();
			qy.Enqueue(0);
			qx.Enqueue(0);
			const int Inf = (int)1e9;

			int[,] dist = new int[1010, 1010];
			for (int i = 0; i < 1010; i++)
			{
				for (int j = 0; j < 1010; j++)
				{
					dist[i, j] = Inf;
				}
			}
			dist[0, 0] = 0;
			int[] dy = { 0, 1, 0, -1 };
			int[] dx = { 1, 0, -1, 0 };
			while (qx.Count > 0)
			{
				int y = qy.Dequeue();
				int x = qx.Dequeue();
				for (int k = 0; k < 4; k++)
				{
					int ny = y + dy[k];
					int nx = x + dx[k];
					if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
					if (k == 0 && imos[y, x] <= 0) continue;
					if (k == 1 && imos2[y, x] <= 0) continue;
					if (k == 2 && imos[ny, nx] <= 0) continue;
					if (k == 3 && imos2[ny, nx] <= 0) continue;
					if (dist[ny, nx] > dist[y, x] + 1)
					{
						dist[ny, nx] = dist[y, x] + 1;
						qy.Enqueue(ny);
						qx.Enqueue(nx);
					}
				}
			}
			int ans = dist[h - 1, w - 1];
			if (ans >= Inf)
			{
				Console.WriteLine("Odekakedekinai..");
			}
			else
			{
				Console.WriteLine(ans);
			}
		}
	}
}
0