#425993 (C#(csc)) No.340 雪の足跡

• 問題: No.340 雪の足跡
• ユーザー: sdfgsjhafs
• 提出日時: 2020-02-04 21:42:46
• 言語: C#(csc) (csc 3.9.0)
• 結果: TLE
• 実行時間: -
• コード長: 11,915 bytes
• コンパイル時間: 1,012 ms
• コンパイル使用メモリ: 121,612 KB
• 実行使用メモリ: 72,232 KB
• 最終ジャッジ日時: 2024-09-21 07:45:07
• 合計ジャッジ時間: 5,209 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 5
other	AC * 9 TLE * 2 -- * 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.Linq;
using System.Text;

// using System.Numerics;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using ll=System.Int64;
using static Contest_D.Lib_IO;
using static Contest_D.Lib_Minifunc;



public static class Contest_D
{

	public static void Main() {
		checked{
			int  w,h,n,dum;
			Lib_IO.rm(out w,out h, out n);
			int[][] b = new int[n][];
			for (int i = 0; i < n; i++)
			{
				rm(out dum);
				ra(out b[i]);	
			}

			HashSet<string> v = new HashSet<string>();
			Dictionary<int,int>[] graph = new Dictionary<int, int>[h*w];
			for (int i = 0; i < h*w; i++)
			{
				graph[i] = new Dictionary<int, int>();
			}
			foreach (var e in b)
			{
				for (int i = 0; i < e.Length-1; i++)
				{
					int x1 = e[i]%w;
					int y1 = e[i]/w;
					int x2 = e[i+1]%w;
					int y2 = e[i+1]/w;
					if(x1==x2){
						if(y1<y2){
							for (int k = (int)y1; k < y2; k++) {
								string ky = (k*w+x1).ToString()+","+((k+1)*w+x1).ToString();
								if(!v.Contains(ky)){
									v.Add(ky);
									graph[k*w+x1][(k+1)*w+x1] = 1;
									graph[(k+1)*w+x1][k*w+x1] = 1;
								}
							}
						}else{
							for (int k = (int)y2; k < y1; k++) {
								string ky = (k*w+x1).ToString()+","+((k+1)*w+x1).ToString();
								if(!v.Contains(ky)){
									v.Add(ky);
									graph[k*w+x1][(k+1)*w+x1] = 1;
									graph[(k+1)*w+x1][k*w+x1] = 1;
								}
							}
						}
					}else{
						if(x1<x2){
							for (int k = (int)x1; k < x2; k++) {
								string ky = (y1*w+k).ToString()+","+(y1*w+k+1).ToString();
								if(!v.Contains(ky)){
									v.Add(ky);
									graph[y1*w+k][y1*w+k+1] = 1;
									graph[y1*w+k+1][y1*w+k] = 1;
								}
							}
						}else{
							for (int k = (int)x2; k < x1; k++) {
								string ky = (y1*w+k).ToString()+","+(y1*w+k+1).ToString();
								if(!v.Contains(ky)){
									v.Add(ky);
									graph[y1*w+k][y1*w+k+1] = 1;
									graph[y1*w+k+1][y1*w+k] = 1;
								}
							}
						}
					}
				}
			}

			var rt = (int)Search(2,h*w,graph,0,0,(int)(h*w-1));
			Lib_IO.wm(rt==-1?"Odekakedekinai..":rt.ToString());
		}
	}
	public static object Search(long stype, long N, IList<Dictionary<int,int>> graph, int startidx, int depth,int goal){
		var que = new ModQue<P<KeyValuePair<int,int>,int>>(stype);
		que.In(new P<KeyValuePair<int,int>, int>(new KeyValuePair<int, int>(startidx,int.MaxValue),depth));  // 第２引数は次のノードに渡す情報を代入（コストの和など）
		var visited = new bool[N]; 
		while(0<que.Count()){
			var cur = que.Out();
			if(visited[cur.A.Key]) continue;
			visited[cur.A.Key]=true;
			var info = cur.B;
			if(cur.A.Key==goal) return info;
			foreach (var e in graph[(int)cur.A.Key]) {
				que.In(new P<KeyValuePair<int,int>, int>(e,info+1));
			}
		}
		return -1;
	}
	public class ModQue<T>{
		readonly public Action Clear;
		readonly public Action<T> In;
		readonly public Func<T> Out, Peek;
		readonly public Func<int> Count;
		public ModQue(long type){
			if(type==1) {
				var S = new Stack<T>();
				Clear = S.Clear; Peek = S.Peek; Count = () => S.Count; In = S.Push; Out = S.Pop;
			}
			if(type==2) {
				var Q = new Queue<T>();
				Clear = Q.Clear; Peek = Q.Peek; Count = () => Q.Count; In = Q.Enqueue; Out = Q.Dequeue;
			}
		}
	}

	public static long[] Dijkstra(P<long,long,long>[] inEdges, long V, long start) {
		long[] dist = Enumerable.Repeat(long.MaxValue, (int)V).ToArray();
		var G = new Dictionary<long,long>[V]; 
		for(int i=0;i<V;i++) G[i] = new Dictionary<long,long>();
		foreach(var e in inEdges){
			G[e.A][e.B] = e.C;
			G[e.B][e.A] = e.C;
		}

		var que = new PriorityQueue<KeyValuePair<long, long>>(V, (x,y)=>(x.Key.CompareTo(y.Key)));
		dist[start] = 0;
		que.Enqueue(new KeyValuePair<long, long>(dist[start], start));
		while(0<que.Count) {
			var q = que.Dequeue();
			if(dist[q.Value] < q.Key) continue;
			foreach(var e in G[q.Value]){
				var next_cost = q.Key + e.Value;
				if(dist[e.Key] <= next_cost) continue;
				dist[e.Key] = next_cost;
				que.Enqueue(new KeyValuePair<long, long>(dist[e.Key], e.Key));
			}
		}
		return dist;
	}

public class PriorityQueue<T>
{
	private readonly List<T> heap;
	private readonly Comparison<T> compare;
	private int size;
	public PriorityQueue() : this(Comparer<T>.Default) {} 
	public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
	public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
	public PriorityQueue(long capacity, Comparison<T> comparison)
	{
		this.heap = new List<T>((int)capacity);
		this.compare = comparison;
	}
	public void Enqueue(T item)
	{
		this.heap.Add(item);
		var i = size++;
		while (i > 0)
		{
			var p = (i - 1) >> 1;
			if (compare(this.heap[p], item) <= 0)
				break;
			this.heap[i] = heap[p];
			i = p;
		}
		this.heap[i] = item;

	}
	public T Dequeue()
	{
		var ret = this.heap[0];
		var x = this.heap[--size];
		var i = 0;
		while ((i << 1) + 1 < size)
		{
			var a = (i << 1) + 1;
			var b = (i << 1) + 2;
			if (b < size && compare(heap[b], heap[a]) < 0) a = b;
			if (compare(heap[a], x) >= 0)
				break;
			heap[i] = heap[a];
			i = a;
		}
		heap[i] = x;
		heap.RemoveAt(size);
		return ret;
	}
	public T Peek() { return heap[0]; }
	public long Count { get { return size; } }
	public bool Any() { return size > 0; }
}















#region BaseModule


public static class Lib_Minifunc{
	[MethodImpl(256)] public static void swap1<T>(ref T a, ref T b) { T t = a; a = b; b = t; }
	[MethodImpl(256)] public static void swap2<T>(ref T a, ref T b) where T : IComparable { if (a.CompareTo(b)==1) swap1(ref a, ref b); }  // b の方が小さければ交換
	[MethodImpl(256)] public static bool chmin<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)== 1) { a = b; return true; } return false; }  // b の方が小さければ a を更新
	[MethodImpl(256)] public static bool chmax<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)==-1) { a = b; return true; } return false; }  // b の方が大きければ a を更新
	[MethodImpl(256)] public static bool inside(long i, long n) => (0<=i&&i<n);
	[MethodImpl(256)] public static bool inside(long x, long y, long w, long h) => (inside(x,w)&&inside(y,h));
	[MethodImpl(256)] public static T min<T>(params T[] a) where T : IComparable => a.Min();
	[MethodImpl(256)] public static T max<T>(params T[] a) where T : IComparable => a.Max();
	[MethodImpl(256)] public static long mod(long a, long m=MOD1) { var v = a%m; return (v<0?v+m:v); }
	[MethodImpl(256)] public static long ceiling(long a, long b) => (a%b==0?a/b:a/b+1);	// 整数商の切り上げ
	[MethodImpl(256)] public static P<T,U> initp<T,U>(T a,U b) => new P<T,U>(a,b);
	[MethodImpl(256)] public static P<T,U,V> initp<T,U,V>(T a,U b,V c) => new P<T,U,V>(a,b,c);
	[MethodImpl(256)] public static P<T,U,V,W> initp<T,U,V,W>(T a,U b,V c,W d) => new P<T,U,V,W>(a,b,c,d);
	[MethodImpl(256)] public static bool initd<T,U>(Dictionary<T,U> d, T k) { if(d.ContainsKey(k)) { return false; } else { d[k] = default(U); return true; } }
	public static T[][] initm<T>(long len1,long len2,T val) where T : struct { var m = new T[len1][]; for (int i=0;i<m.Length;i++) m[i] = Enumerable.Repeat(val,(int)len2).ToArray(); return m; }
	public static T[][][] initm<T>(long len1,long len2,long len3,T val) where T : struct { var m = new T[len1][][]; for (int i=0;i<m.Length;i++) m[i] = initm(len2,len3,val); return m; }
	public const long MOD1 = 1000000007; // 10^9+7
	public const double EPS1 = 1e-8;
	public const long INF1 = 1000000000000000;  // 10^15
}

public struct P<T,U>
{
	public T A; public U B;
	public P(T a,U b) { A = a; B = b; }
	public static implicit operator KeyValuePair<T,U>(P<T,U> a) => new KeyValuePair<T,U>(a.A,a.B);
	public static implicit operator P<T,U>(KeyValuePair<T,U> a) => new P<T,U>(a.Key,a.Value);
}
public struct P<T,U,V>
{
	public T A; public U B; public V C;
	public P(T a,U b,V c) { A = a; B = b; C = c; }
}
public struct P<T,U,V,W>
{
	public T A; public U B; public V C; public W D;
	public P(T a,U b,V c,W d) { A = a; B = b; C = c; D = d; }
}

public static class Lib_IO
{
	class Prt : System.IO.StreamWriter
	{
		public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } }
		public Prt(System.IO.Stream s) : base(s,new UTF8Encoding(false,true)) {}
		public Prt(System.IO.Stream s,Encoding e) : base(s,e) {}
	}
	static Prt sw = new Prt(Console.OpenStandardOutput());
	static char[] sp = new char[] {' '};
	[MethodImpl(256)] static bool eq<T,U>() => typeof(T).Equals(typeof(U));
	[MethodImpl(256)] static T ct<T,U>(U a) => (T)Convert.ChangeType(a,typeof(T));
	[MethodImpl(256)] static T cv<T>(string s) =>
		eq<T,int>()	? ct<T,int>(int.Parse(s))
	  : eq<T,long>()   ? ct<T,long>(long.Parse(s))
	  : eq<T,double>() ? ct<T,double>(double.Parse(s,System.Globalization.CultureInfo.InvariantCulture))
	  : eq<T,char>()   ? ct<T,char>(s[0])
					   : ct<T,string>(s);
	public static string[] rm<T>(out T a) {
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); 
		a = cv<T>(z[0]);
		return z;
	}
	public static string[] rm<T,U>(out T a,out U b) {
		var z = rm<T>(out a); 
		b = cv<U>(z[1]);
		return z;
	}
	public static string[] rm<T,U,V>(out T a,out U b,out V c) {
		var z = rm<T,U>(out a,out b); 
		c = cv<V>(z[2]);
		return z;
	}
	public static string[] rm<T,U,V,W>(out T a,out U b,out V c,out W d) {
		var z = rm<T,U,V>(out a,out b,out c); 
		d = cv<W>(z[3]);
		return z;
	}
	public static string[] rm<T,U,V,W,X>(out T a,out U b,out V c,out W d,out X e) {
		var z = rm<T,U,V,W>(out a,out b,out c,out d); 
		e = cv<X>(z[4]);
		return z;
	}
	public static string[] rm<T,U,V,W,X,Y>(out T a,out U b,out V c,out W d,out X e,out Y f) {
		var z = rm<T,U,V,W,X>(out a,out b,out c,out d,out e); 
		f = cv<Y>(z[5]);
		return z;
	}
	public static string[] ra<T>(out T[] a) {		
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries);
		a = z.Select(cv<T>).ToArray();
		return z;
	}
	public static string[][] rl<T>(long n,out T[] a) {
		a = new T[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = rm(out a[i]);
		return y;
	}
	public static string[][] rl<T,U>(long n,out P<T,U>[] a) {
		a = new P<T,U>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p;
			y[i] = rm(out o,out p);
			a[i] = new P<T,U>(o,p);
		}
		return y;
	}
	public static string[][] rl<T,U,V>(long n,out P<T,U,V>[] a) {
		a = new P<T,U,V>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q;
			y[i] = rm(out o,out p,out q);
			a[i] = new P<T,U,V>(o,p,q);
		}
		return y;
	}
	public static string[][] rl<T,U,V,W>(long n,out P<T,U,V,W>[] a) {
		a = new P<T,U,V,W>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q; W r;
			y[i] = rm(out o,out p,out q,out r);
			a[i] = new P<T,U,V,W>(o,p,q,r);
		}
		return y;
	}
	public static string[][] rx<T>(long n,out T[][] a) {
		a = new T[n][];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = ra(out a[i]);
		return y;
	}

	static void wwp(Action act){
		sw.AutoFlush = false;
		Console.SetOut(sw);
		act();
		Console.Out.Flush();
		sw.AutoFlush = true;
		Console.SetOut(sw);
	}
	[MethodImpl(256)] static string wfm(Type t) =>t.Equals(typeof(double)) ? "{0:F10}" : "{0}";
	public static void wm(params object[] a) {
		wwp(()=>{
			for(int i=0;i<a.Length;i++) {
				var f = wfm(a[i].GetType()) + ((i<a.Length-1) ? " " : Environment.NewLine);
				Console.Write(f,a[i]);
			}
		});
	}
	public static void wa<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T));
			var g = f + " ";
			var h = f + Environment.NewLine;
			for(int i=0;i<a.Count;i++) Console.Write(((i<a.Count-1) ? g : h),a[i]);
		});
	}
	public static void wl<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T)) + Environment.NewLine;
			foreach(T x in a) Console.Write(f,x);
		});
	}
}

#endregion



}