No.157 2つの空洞

■■■問題■■■

壁'#'と空洞'.'からなる横の幅がW、縦の幅がHの空間がある。
調べたところ壁の中に空洞のかたまりが2つあることがわかった。
壁'#'をいくつかどけることで2つの空洞のかたまりをつなげたい。
最小でいくつの壁'#'をどければ良いかを答えよ。

■■■入力■■■

W H
C0,0C1,0・・・CW-1,0
C0,1C1,1・・・CW-1,1
・・・
C0,H-1C1,H-1・・・CW-1,H-1

Wは横幅,Hは縦幅をあらわす。W,Hはともに整数。(1 <= W,H <= 20)
Cxyはその位置が壁があるか空洞かをあらわす。
壁は'#'であらわされ、空洞は'.'であらわされる。

空洞は縦か横に接しているとつながっているとし、斜めではつながらない。
空洞のかたまりはちょうど2つあることが保証される。
また、空洞のかたまりはかならず壁'#'で囲われることが保証される。

■■■出力■■■

どける必要のある壁の最小の数を1行で答えよ。
最後に改行してください。

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("9 5");
            WillReturn.Add("#########");
            WillReturn.Add("#.####.##");
            WillReturn.Add("#..###.##");
            WillReturn.Add("#..###..#");
            WillReturn.Add("#########");
            //3
            //左と右に空洞のかたまりが1つずつある。
            //壁を3つどければ2つの空洞はつながる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 5");
            WillReturn.Add("########");
            WillReturn.Add("####..##");
            WillReturn.Add("#..#..##");
            WillReturn.Add("#...####");
            WillReturn.Add("########");
            //1
            //壁を1つどければ2つの空洞はつながる。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 9");
            WillReturn.Add("#########");
            WillReturn.Add("#.......#");
            WillReturn.Add("#.#####.#");
            WillReturn.Add("#.#...#.#");
            WillReturn.Add("#.#.#.#.#");
            WillReturn.Add("#.#...#.#");
            WillReturn.Add("#.#####.#");
            WillReturn.Add("#.......#");
            WillReturn.Add("#########");
            //1
            //このような図も2つの空洞とみなします。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 6");
            WillReturn.Add("########");
            WillReturn.Add("#....###");
            WillReturn.Add("#.######");
            WillReturn.Add("#.####.#");
            WillReturn.Add("#.######");
            WillReturn.Add("########");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }
    //空白座標の配列
    static List<PointDef> SpacePointList;
    //連結空白をまとめた配列
    static PointDef[] RenketuSpacePointArr;

    static int UB_X;
    static int UB_Y;

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

        UB_X = InputList[1].Length - 1;
        UB_Y = InputList.Count - 1;

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

        PrintBan(BanArr);

        //空白座標のListを作成
        SpacePointList = DeriveSpacePointList(BanArr);

        //連結空白をまとめた配列
        RenketuSpacePointArr = DeriveRenketuSpacePointArr(BanArr);

        Console.WriteLine("連結した空白の配列は");
        foreach (PointDef EachPoint in RenketuSpacePointArr) {
            Console.Write("({0},{1}),", EachPoint.X, EachPoint.Y);
        }
        Console.WriteLine();

        int Answer = int.MaxValue;

        //片方の空洞の連結空白をRemove
        SpacePointList.RemoveAll(A => Array.Exists(RenketuSpacePointArr,
                                      B => B.X == A.X && B.Y == A.Y));

        foreach (PointDef EachPoint1 in RenketuSpacePointArr) {
            foreach (PointDef EachPoint2 in SpacePointList) {
                //マンハッタン距離を求める
                int wkKyori = Math.Abs(EachPoint1.X - EachPoint2.X);
                wkKyori += Math.Abs(EachPoint1.Y - EachPoint2.Y);

                if (Answer > wkKyori)
                    Answer = wkKyori;
            }
        }
        Console.WriteLine(Answer - 1);
    }

    //空白座標のListを作成
    static List<PointDef> DeriveSpacePointList(char[,] pBanArr)
    {
        var WillReturn = new List<PointDef>();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                if (pBanArr[LoopX, LoopY] != '.') continue;
                WillReturn.Add(new PointDef() { X = LoopX, Y = LoopY });
            }
        }
        return WillReturn;
    }

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

    //UnionFindで連結空白をまとめた配列を返す
    static PointDef[] DeriveRenketuSpacePointArr(char[,] pBanArr)
    {
        var VisitedList = new List<PointDef>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = SpacePointList[0].X;
        WillPush.CurrY = SpacePointList[0].Y;
        stk.Push(WillPush);
        VisitedList.Add(SpacePointList[0]);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

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

                if (pBanArr[pNewX, pNewY] != '.') return;

                //再訪不可
                if (VisitedList.Exists(A => A.X == pNewX && A.Y == pNewY))
                    return;
                VisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                stk.Push(WillPush);
            };

            PushAct(Popped.CurrX, Popped.CurrY - 1);
            PushAct(Popped.CurrX, Popped.CurrY + 1);
            PushAct(Popped.CurrX - 1, Popped.CurrY);
            PushAct(Popped.CurrX + 1, Popped.CurrY);
        }

        return VisitedList.ToArray();
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

デバッグ情報付の実行結果

#########
#.####.##
#..###.##
#..###..#
#########

連結した空白の配列は
(1,1),(1,2),(1,3),(2,2),(2,3),
3

解説

最初に、任意の1つの空白からUnionFindで連結空白の配列を作成します。

次に、それらの連結空白と連結空白でない空白座標との
マンハッタン距離の最小値を求めてます。