結果

問題 No.340 雪の足跡
コンテスト
ユーザー pekempey
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
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