ABC-088-D Grid Repainting

■■■問題■■■

縦Hマス、横Wマスに広がるマス目があり、各マスは白または黒で塗られている。
上からi番目で左からj番目のマスを(i,j)で表す。

すぬけ君は、このマス目を使って次のようなゲームをしたい。
ゲームの開始時点ではマス(1,1)にゲームキャラクター「けぬす君」がいる。
プレイヤーはけぬす君を上下左右の4方向のいずれかに1マスだけ動かすことを繰り返す。
けぬす君が白いマスだけを通って(H,W)にたどり着けばゲームクリアとなる。

ゲームを開始する前に、すぬけ君はいくつかの白いマス目の色を黒に変えることができる。
ただし、マス(1,1)と(H,W)の色を変えることはできず、
ゲームを開始するまでにすべての色の変更を行わなければならない。

ゲームをクリアしたとき、ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる。
そのとき、すぬけ君が取る可能性のある最大のスコアを求めなさい。
ただし、すぬけ君がどのようにマス目の色を変えてもけぬす君が(H,W)にたどり着くことが出来ない場合、
-1と出力しなさい。

ただし、各マスの色の情報は文字 si,jとして与えられる。
マス(i,j)が最初白で塗られている場合 si,j は.であり、
マス(i,j)が最初黒で塗られている場合 si,j は#である。

■■■入力■■■

H W
s1,1s1,2s1,3 ・・・ s1,W
s2,1s2,2s2,3 ・・・ s2,W
・
・
・
sH,1sH,2sH,3 ・・・ sH,W

●Hは2以上50以下の整数
●Wは2以上50以下の整数
●si,j は . または # (1 <= i <= H,1 <= j <= W)
●s1,1,sH,W は . である

■■■出力■■■

すぬけ君が取る可能性のある最大のスコアを出力しなさい。
ただし、すぬけ君がどのようにマス目の色を変えてもけぬす君が(H,W)にたどり着くことが出来ない場合、
-1と出力しなさい。

■■■サンプルケースのイメージ■■■

■入出力例1のイメージ■
下の図のようにマス目の色を変えれば、スコア2を達成できます。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 3");
            WillReturn.Add("..#");
            WillReturn.Add("#..");
            WillReturn.Add("...");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 37");
            WillReturn.Add(".....................................");
            WillReturn.Add("...#...####...####..###...###...###..");
            WillReturn.Add("..#.#..#...#.##....#...#.#...#.#...#.");
            WillReturn.Add("..#.#..#...#.#.....#...#.#...#.#...#.");
            WillReturn.Add(".#...#.#..##.#.....#...#.#.###.#.###.");
            WillReturn.Add(".#####.####..#.....#...#..##....##...");
            WillReturn.Add(".#...#.#...#.#.....#...#.#...#.#...#.");
            WillReturn.Add(".#...#.#...#.##....#...#.#...#.#...#.");
            WillReturn.Add(".#...#.####...####..###...###...###..");
            WillReturn.Add(".....................................");
            //209
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int Level;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int UB_X = wkArr[1] - 1;
        int UB_Y = wkArr[0] - 1;

        char[,] BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                BanArr[X, Y] = InputList[Y + 1][X];
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = 0;
        WillEnqueue.CurrY = 0;
        WillEnqueue.Level = 1;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(0 * (UB_Y + 1) + 0);

        int WhiteCnt = BanArr.Cast<char>().Count(X => X == '.');

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア判定
            if (Dequeued.CurrX == UB_X && Dequeued.CurrY == UB_Y) {
                Console.WriteLine(WhiteCnt - Dequeued.Level);
                return;
            }

            Action<int, int> EnqueAct = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                if (BanArr[pNewX, pNewY] == '#') return;

                //再訪防止
                if (VisitedSet.Add(pNewX * (UB_Y + 1) + pNewY) == false)
                    return;

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.Level = Dequeued.Level + 1;
                Que.Enqueue(WillEnqueue);
            };

            EnqueAct(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueAct(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueAct(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueAct(Dequeued.CurrX + 1, Dequeued.CurrY);
        }
        Console.WriteLine(-1);
    }
}

解説

幅優先探索で最短経路を求めてます。