結果

問題 No.340 雪の足跡
ユーザー pekempeypekempey
提出日時 2016-01-29 23:56:58
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 706 ms / 1,000 ms
コード長 2,660 bytes
コンパイル時間 1,020 ms
コンパイル使用メモリ 110,352 KB
実行使用メモリ 56,432 KB
最終ジャッジ日時 2023-10-21 17:36:32
合計ジャッジ時間 12,606 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
36,352 KB
testcase_01 AC 84 ms
36,352 KB
testcase_02 AC 82 ms
35,860 KB
testcase_03 AC 85 ms
36,352 KB
testcase_04 AC 84 ms
36,352 KB
testcase_05 AC 82 ms
35,860 KB
testcase_06 AC 84 ms
36,352 KB
testcase_07 AC 84 ms
36,352 KB
testcase_08 AC 83 ms
36,352 KB
testcase_09 AC 85 ms
36,352 KB
testcase_10 AC 85 ms
36,352 KB
testcase_11 AC 90 ms
36,632 KB
testcase_12 AC 90 ms
36,632 KB
testcase_13 AC 91 ms
36,632 KB
testcase_14 AC 115 ms
40,832 KB
testcase_15 AC 122 ms
40,832 KB
testcase_16 AC 112 ms
40,832 KB
testcase_17 AC 131 ms
40,832 KB
testcase_18 AC 122 ms
40,828 KB
testcase_19 AC 129 ms
40,832 KB
testcase_20 AC 504 ms
48,088 KB
testcase_21 AC 394 ms
49,712 KB
testcase_22 AC 82 ms
35,860 KB
testcase_23 AC 583 ms
55,704 KB
testcase_24 AC 466 ms
56,432 KB
testcase_25 AC 503 ms
51,420 KB
testcase_26 AC 157 ms
42,088 KB
testcase_27 AC 101 ms
38,696 KB
testcase_28 AC 151 ms
46,768 KB
testcase_29 AC 594 ms
56,236 KB
testcase_30 AC 385 ms
43,872 KB
testcase_31 AC 610 ms
55,528 KB
testcase_32 AC 705 ms
56,212 KB
testcase_33 AC 520 ms
46,460 KB
testcase_34 AC 706 ms
56,268 KB
testcase_35 AC 601 ms
54,792 KB
testcase_36 AC 600 ms
54,844 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