ARC-031-B 埋め立て

■■■問題■■■

とある所に島国がありました。島国にはいくつかの島があります。
このたび、この島国で埋め立て計画が立案されたのですが、
どこを埋め立てるか決まっていません。

できることなら埋め立てによって島を繋いで、
1つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。

10マス × 10マスのこの島国の地図が与えられるので、
1マスを埋め立てた時に1つの島にできるか判定してください。
ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。 

■■■入力■■■

A1,1A1,2 ・・・ A1,10
A2,1A2,2 ・・・ A2,10
・
・
・
A10,1A10,2 ・・・ A10,10

●島国の地図が10行にわたって与えられる。
●各行は10文字からなり、oは陸地を、xは海を表す。
●少なくとも1マスは陸地があることが保証される。
●少なくとも1マスは海があることが保証される。

■■■出力■■■

海を1マスだけ陸地にすることで全体を1つの島にできるならYES、
できないならNOを出力せよ。出力の末尾には改行をつけること。
ただし、元から1つの島だった場合も YES を出力せよ。

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

入出力例1のイメージ
赤く囲ったマスを埋め立てることで1つの島にできます

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xoooooooxx");
            WillReturn.Add("xxoooooxxx");
            WillReturn.Add("xxxoooxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxoooxxxx");
            WillReturn.Add("xxoooooxxx");
            WillReturn.Add("xxxxxxxxxx");
            //YES
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xoooooooxx");
            WillReturn.Add("xxoooooxxx");
            WillReturn.Add("xxxoooxxxx");
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xxxxxxxxxx");
            WillReturn.Add("xxxoooxxxx");
            WillReturn.Add("xxoooooxxx");
            WillReturn.Add("xxxxxxxxxx");
            //NO
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("ooooxooooo");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            WillReturn.Add("xxxxoxxxxx");
            //YES
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int UB = 10 - 1;

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

        char[,] BanArr = new char[UB + 1, UB + 1];
        int wkRikuCnt = 0;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                BanArr[X, Y] = InputList[Y][X];
                if (BanArr[X, Y] == 'o') wkRikuCnt++;
            }
        }

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                //海でない場合
                if (BanArr[X, Y] != 'x') continue;

                if (ExecUnionFind(BanArr, X, Y, wkRikuCnt + 1)) {
                    Console.WriteLine("YES");
                    return;
                }
            }
        }
        Console.WriteLine("NO");
    }

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

    //UnionFindして、全ての陸地に到達可能かを返す
    static bool ExecUnionFind(char[,] pBanArr, int pStaX, int pStaY, int pRikuCnt)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = pStaX;
        WillPush.CurrY = pStaY;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(string.Format("{0},{1}", pStaX, pStaY));

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

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB < pNewX) return;
                if (pNewY < 0 || UB < pNewY) return;

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

                string wkStr = string.Format("{0},{1}", pNewX, pNewY);
                if (VisitedSet.Add(wkStr)) {
                    WillPush.CurrX = pNewX;
                    WillPush.CurrY = pNewY;
                    Stk.Push(WillPush);
                }
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        return VisitedSet.Count == pRikuCnt;
    }
}

解説

10*10で、100回深さ優先探索してます。