第10回日本情報オリンピック予選（オンライン）E - チーズ (Cheese)

1→2→…→N と順番に辿っていけばいい。答えは「(S から 1 までの距離) + (1 から 2 までの距離) + … + (N - 1 から N までの距離)」になるので、幅優先探索による全探索を、開始地点を変えながら繰り返す。

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

namespace JOI2011YO_E
{
    class Program
    {
        static void Main(string[] args)
        {
            var HWN = Console.ReadLine().Split(' ');
            var H = int.Parse(HWN[0]);
            var W = int.Parse(HWN[1]);
            var N = int.Parse(HWN[2]);
            var grid = new List<string>();
            Point? s = null;
            for (var y = 0; y < H; y++)
            {
                var row = Console.ReadLine();
                grid.Add(row);

                if (s == null)
                {
                    for (var x = 0; x < row.Length; x++)
                    {
                        if (row[x] == 'S')
                        {
                            s = new Point(x, y);
                        }
                    }
                }
            }

            // S から 1 までの距離を幅優先探索で計測
            // 1 から 2 までの距離を幅優先探索で計測
            // …
            // N - 1 から N までの距離を幅優先探索で計測
            var answer = 0;
            for (var goal = '1'; goal <= '0' + N; goal++)
            {
                var dist = new List<List<int>>();
                for (var i = 0; i < H; i++)
                {
                    dist.Add(Enumerable.Repeat(-1, W).ToList());
                }

                var queue = new Queue<Point>();
                queue.Enqueue(s.Value);
                dist[s.Value.y][s.Value.x] = 0;
                while (queue.Count > 0)
                {
                    var current = queue.Dequeue();
                    foreach (var next in current.GetNext())
                    {
                        if (next.x >= 0 &&
                            next.x < W &&
                            next.y >= 0 &&
                            next.y < H &&
                            grid[next.y][next.x] != 'X' &&
                            dist[next.y][next.x] == -1)
                        {
                            dist[next.y][next.x] = dist[current.y][current.x] + 1;
                            if (grid[next.y][next.x] == goal)
                            {
                                answer += dist[next.y][next.x];
                                s = next;
                                queue.Clear();
                                break;
                            }
                            else
                            {
                                queue.Enqueue(next);
                            }
                        }
                    }
                }
            }

            Console.WriteLine(answer);
        }
    }

    readonly struct Point
    {
        public Point(int x, int y) => (this.x, this.y) = (x, y);
        public readonly int x;
        public readonly int y;

        public IEnumerable<Point> GetNext()
        {
            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);
        }
    }
}