Submission #39262599

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;

namespace xxx
{
    internal class Program
    {
        static void Main(string[] args)
        {
            AL.SetCase();
            var (N, M) = AL.ReadInt2();
            var S = new List<List<int>>();
            S.Add(new List<int>());//S[0] dummy
            for (int i = 0; i < N; i++)
            {
                var s = new List<int>();
                var ics = AL.ReadIntChars();
                for (int j = 0; j < ics.Length; j++)
                {
                    if (ics[j] ==1)
                    {
                        s.Add(j+1);
                    }
                }
                S.Add(s);
            }

            // スタートからのコストを計算
            var costFromStart = Enumerable.Repeat<int>(1000000, N+1).ToArray();
            costFromStart[1] = 0;
            for (int i = 1; i <= N; i++)
            {
                var s = S[i];
                var cost = costFromStart[i] + 1;
                foreach (var span in s)
                {
                    var dst = i + span;
                    if (dst > N) continue;
                    costFromStart[dst] = Math.Min(costFromStart[dst], cost);
                }
            }

            // ゴールからのコストを計算
            var costFromGoal = Enumerable.Repeat<int>(1000000, N + 1).ToArray();
            costFromGoal[N] = 0;
            for (int i = N - 1; i >= 1; i--)
            {
                var s = S[i];
                foreach (var span in s)
                {
                    var dst = i + span;
                    if (dst > N) continue;
                    costFromGoal[i] = Math.Min(costFromGoal[dst]+1, costFromGoal[i]);
                }
            }

            var anss = new List<int>();
            for (int k = 2; k < N; k++)
            {
                int mincost = 1000000;
                for (int start = k + 1 - M; start < k; start++)
                {
                    if (start < 1) continue;
                    var s = S[start];
                    foreach (var span in s)
                    {
                        var dst = start + span;
                        if (dst <= k) continue;
                        if (dst > N) continue;
                        int cost = costFromStart[start] + costFromGoal[dst] + 1;
                        if (cost < mincost)
                        {
                            mincost = cost;
                        }
                    }

                }
                if (mincost >= 1000000)
                {
                    mincost = -1;
                }
                anss.Add(mincost);
            }
            Console.WriteLine(string.Join(" ", anss.Select(a => a.ToString())));
        }
    }
    static class AL
    {
        public static void SetCase()
        {
#if DEBUG
            Console.WriteLine("Case?");
            var name = Console.ReadLine();
            if (string.IsNullOrWhiteSpace(name))
            {
                Console.WriteLine("Using stdin");
                return;
            }
            var exStdIn = new System.IO.StreamReader($"../../../{name}.txt");
            System.Console.SetIn(exStdIn);
#endif
        }
        public static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        public static int[] ReadIntChars()
        {
            // 102 => int[]{1, 0, 2}
            return Console.ReadLine().ToCharArray().Select(c => int.Parse(c.ToString())).ToArray();
        }


        public static int[] ReadIntArray()
        {
            // 12 34 56 => int[]{12, 34, 56}
            return Console.ReadLine().Split().Select(int.Parse).ToArray();
        }

        public static (int a, int b) ReadInt2()
        {
            var ia = ReadIntArray();
            if (ia.Length != 2)
            {
                throw new InvalidCastException();
            }
            return (ia[0], ia[1]);
        }
        public static (int a, int b, int c) ReadInt3()
        {
            var ia = ReadIntArray();
            if (ia.Length != 3)
            {
                throw new InvalidCastException();
            }
            return (ia[0], ia[1], ia[2]);
        }
    }
    public class DefaultDictionary<TKey, TValue> : Dictionary<TKey, TValue> where TValue : new()
    {
        public new TValue this[TKey key]
        {
            get
            {
                if (!TryGetValue(key, out TValue val))
                {
                    val = new TValue();
                    Add(key, val);
                }
                return val;
            }
            set { base[key] = value; }
        }
    }
}

Submission Info

Judge Result