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{ long w,h,n,dum; Lib_IO.rm(out w,out h, out n); ll[][] b = new ll[n][]; for (int i = 0; i < n; i++) { rm(out dum); ra(out b[i]); } bool[][] g = initm(h,w,false); bool[][] v = initm(h*w,h*w,false); List> edge = new List>(); foreach (var e in b) { for (int i = 0; i < e.Length-1; i++) { ll x1 = e[i]%w; ll y1 = e[i]/w; ll x2 = e[i+1]%w; ll y2 = e[i+1]/w; if(x1==x2){ if(y1(k*w+x1,(k+1)*w+x1,1)); } } }else{ for (int k = (int)y2; k < y1; k++) { g[k][x1] = true; if(!v[k*w+x1][(k+1)*w+x1]){ v[k*w+x1][(k+1)*w+x1] = true; v[(k+1)*w+x1][k*w+x1] = true; edge.Add(new P(k*w+x1,(k+1)*w+x1,1)); } } } }else{ if(x1(y1*w+k,y1*w+k+1,1)); } } }else{ for (int k = (int)x2; k < x1; k++) { g[y1][k] = true; if(!v[y1*w+k][y1*w+k+1]){ v[y1*w+k][y1*w+k+1] = true; v[y1*w+k+1][y1*w+k] = true; edge.Add(new P(y1*w+k,y1*w+k+1,1)); } } } } } } ll[] pr; var rt = Dijkstra(edge.ToArray(), h*w, 0, out pr); Lib_IO.wm(int.MaxValue[] inEdges, long V, long start, out long[] prev) { long[] dist = Enumerable.Repeat(long.MaxValue, (int)V).ToArray(); prev = Enumerable.Repeat(-1L, (int)V).ToArray(); var G = new Dictionary[V]; for(int i=0;i(); foreach(var e in inEdges){ G[e.A][e.B] = e.C; G[e.B][e.A] = e.C; } var que = new PriorityQueue>(V, (x,y)=>(x.Key.CompareTo(y.Key))); dist[start] = 0; que.Enqueue(new KeyValuePair(dist[start], start)); while(0(dist[e.Key], e.Key)); prev[e.Key] = q.Value; } } return dist; } public class PriorityQueue { private readonly List heap; private readonly Comparison compare; private int size; public PriorityQueue() : this(Comparer.Default) {} public PriorityQueue(IComparer comparer) : this(16, comparer.Compare) { } public PriorityQueue(Comparison comparison) : this(16, comparison) { } public PriorityQueue(long capacity, Comparison comparison) { this.heap = new List((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(ref T a, ref T b) { T t = a; a = b; b = t; } [MethodImpl(256)] public static void swap2(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(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(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 (inside(x,w)&&inside(y,h)); [MethodImpl(256)] public static T min(params T[] a) where T : IComparable => a.Min(); [MethodImpl(256)] public static T max(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 initp(T a,U b) => new P(a,b); [MethodImpl(256)] public static P initp(T a,U b,V c) => new P(a,b,c); [MethodImpl(256)] public static P initp(T a,U b,V c,W d) => new P(a,b,c,d); [MethodImpl(256)] public static bool initd(Dictionary d, T k) { if(d.ContainsKey(k)) { return false; } else { d[k] = default(U); return true; } } public static T[][] initm(long len1,long len2,T val) where T : struct { var m = new T[len1][]; for (int i=0;i(long len1,long len2,long len3,T val) where T : struct { var m = new T[len1][][]; for (int i=0;i { public T A; public U B; public P(T a,U b) { A = a; B = b; } public static implicit operator KeyValuePair(P a) => new KeyValuePair(a.A,a.B); public static implicit operator P(KeyValuePair a) => new P(a.Key,a.Value); } public struct P { 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 { 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() => typeof(T).Equals(typeof(U)); [MethodImpl(256)] static T ct(U a) => (T)Convert.ChangeType(a,typeof(T)); [MethodImpl(256)] static T cv(string s) => eq() ? ct(int.Parse(s)) : eq() ? ct(long.Parse(s)) : eq() ? ct(double.Parse(s,System.Globalization.CultureInfo.InvariantCulture)) : eq() ? ct(s[0]) : ct(s); public static string[] rm(out T a) { var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); a = cv(z[0]); return z; } public static string[] rm(out T a,out U b) { var z = rm(out a); b = cv(z[1]); return z; } public static string[] rm(out T a,out U b,out V c) { var z = rm(out a,out b); c = cv(z[2]); return z; } public static string[] rm(out T a,out U b,out V c,out W d) { var z = rm(out a,out b,out c); d = cv(z[3]); return z; } public static string[] rm(out T a,out U b,out V c,out W d,out X e) { var z = rm(out a,out b,out c,out d); e = cv(z[4]); return z; } public static string[] rm(out T a,out U b,out V c,out W d,out X e,out Y f) { var z = rm(out a,out b,out c,out d,out e); f = cv(z[5]); return z; } public static string[] ra(out T[] a) { var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); a = z.Select(cv).ToArray(); return z; } public static string[][] rl(long n,out T[] a) { a = new T[n]; var y = new string[n][]; for(int i=0;i(long n,out P[] a) { a = new P[n]; var y = new string[n][]; for(int i=0;i(o,p); } return y; } public static string[][] rl(long n,out P[] a) { a = new P[n]; var y = new string[n][]; for(int i=0;i(o,p,q); } return y; } public static string[][] rl(long n,out P[] a) { a = new P[n]; var y = new string[n][]; for(int i=0;i(o,p,q,r); } return y; } public static string[][] rx(long n,out T[][] a) { a = new T[n][]; var y = new string[n][]; for(int i=0;it.Equals(typeof(double)) ? "{0:F10}" : "{0}"; public static void wm(params object[] a) { wwp(()=>{ for(int i=0;i(IList a) { wwp(()=>{ var f = wfm(typeof(T)); var g = f + " "; var h = f + Environment.NewLine; for(int i=0;i(IList a) { wwp(()=>{ var f = wfm(typeof(T)) + Environment.NewLine; foreach(T x in a) Console.Write(f,x); }); } } #endregion }