AGC033A - Darker and Darker

開始地点となる # の位置を記録しておいて、まとめて幅優先探索を行う。一つずつ幅優先探索を完了していったらタイムオーバーになるので、まとめてやるのが重要だった。

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

namespace AGC033A
{
    class Program
    {
        static void Main(string[] args)
        {
            var HW = Console.ReadLine().Split(' ');
            var H = int.Parse(HW[0]);
            var W = int.Parse(HW[1]);
            var A = new List<string>();
            var starts = new List<Point>();
            for (var y = 0; y < H; y++)
            {
                var row = Console.ReadLine();
                A.Add(row);
                for (var x = 0; x < row.Length; x++)
                {
                    if (row[x] == '#')
                    {
                        starts.Add(new Point(x, y));
                    }
                }
            }

            var dist = Enumerable.Range(0, H)
                .Select(x => Enumerable.Repeat(-1, W).ToList())
                .ToList();
            var queue = new Queue<Point>();
            foreach (var start in starts)
            {
                queue.Enqueue(start);
                dist[start.Y][start.X] = 0;
            }
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                foreach (var next in current.GetNexts())
                {
                    if (next.X >= 0 &&
                        next.X < W &&
                        next.Y >= 0 &&
                        next.Y < H &&
                        A[next.Y][next.X] == '.' &&
                        dist[next.Y][next.X] == -1)
                    {
                        dist[next.Y][next.X] = dist[current.Y][current.X] + 1;
                        queue.Enqueue(next);
                    }
                }
            }

            var answer = dist.SelectMany(x => x).Max();
            Console.WriteLine(answer);
        }
    }

    readonly struct Point
    {
        public readonly int X;

        public readonly int Y;

        public Point(int x, int y) => (X, Y) = (x, y);

        public IEnumerable<Point> GetNexts()
        {
            yield return new Point(X - 1, Y);
            yield return new Point(X + 1, Y);
            yield return new Point(X, Y - 1);
            yield return new Point(X, Y + 1);
        }
    }
}