ABC088D - Grid Repainting

幅優先探索でスタート地点からの距離を測ってみた。ゴール地点の距離が判明していたら到達可能と判断できる。

ゴール地点の距離 + 1 が必須の白いマスで、それ以外の白いマスは黒に塗りつぶせる。あらかじめ白いマスの数を数えておき、ゴール地点の距離 + 1 を引けばいい。

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

namespace ABC088D
{
    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 grid = new List<string>();
            var dist = new List<List<int>>();
            var whiteCount = 0; 
            for (var i = 0; i < H; i++)
            {
                var row = Console.ReadLine();
                grid.Add(row);
                whiteCount += row.Count(c => c == '.');
                dist.Add(new List<int>(Enumerable.Repeat(-1, W)));
            }

            dist[0][0] = 0;
            var queue = new Queue<(int x, int y)>();
            queue.Enqueue((0, 0));
            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                foreach (var next in GetNext(current))
                {
                    if (next.x >= 0 &&
                        next.x < W &&
                        next.y >= 0 &&
                        next.y < H &&
                        dist[next.y][next.x] == -1 &&
                        grid[next.y][next.x] == '.')
                    {
                        dist[next.y][next.x] = dist[current.y][current.x] + 1;
                        queue.Enqueue(next);
                    }
                }
            }

            var answer = -1;
            var goalDist = dist[H - 1][W - 1];
            if (goalDist != -1)
            {
                answer = whiteCount - goalDist - 1;
            }
            Console.WriteLine(answer);
        }

        static IEnumerable<(int x, int y)> GetNext((int x, int y) c)
        {
            yield return (c.x - 1, c.y);
            yield return (c.x + 1, c.y);
            yield return (c.x, c.y - 1);
            yield return (c.x, c.y + 1);
        }
    }
}