ABC269-D Do use hexagon grid

問題へのリンク

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("6");
            WillReturn.Add("-1 -1");
            WillReturn.Add("0 1");
            WillReturn.Add("0 2");
            WillReturn.Add("1 0");
            WillReturn.Add("1 2");
            WillReturn.Add("2 0");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("5 0");
            WillReturn.Add("4 1");
            WillReturn.Add("-3 -4");
            WillReturn.Add("-2 -5");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("2 1");
            WillReturn.Add("2 -1");
            WillReturn.Add("1 0");
            WillReturn.Add("3 1");
            WillReturn.Add("1 -1");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYInfoDef
    {
        internal int X;
        internal int Y;
    }
    static List<XYInfoDef> mXYList = new List<XYInfoDef>();
    static HashSet<int> mXYSet = new HashSet<int>();

    // 連結成分のID[ノードID]なDict
    static Dictionary<int, int> mTreeDict = new Dictionary<int, int>();

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYInfoDef WillAdd;
            WillAdd.X = wkArr[0] + 3000;
            WillAdd.Y = wkArr[1] + 3000;
            mXYList.Add(WillAdd);

            int Hash = GetHash(WillAdd.X, WillAdd.Y);
            mXYSet.Add(Hash);
        }
        ExecDFS();

        Console.WriteLine(mTreeDict.Values.Distinct().Count());
    }

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

    // 深さ優先探索を行う
    static void ExecDFS()
    {
        for (int I = 0; I <= mXYList.Count - 1; I++) {
            int RootHash = GetHash(mXYList[I].X, mXYList[I].Y);
            if (mTreeDict.ContainsKey(RootHash)) continue;

            var Stk = new Stack<JyoutaiDef>();
            JyoutaiDef WillPush;
            WillPush.CurrX = mXYList[I].X;
            WillPush.CurrY = mXYList[I].Y;
            Stk.Push(WillPush);
            mTreeDict[RootHash] = RootHash;

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

                Action<int, int> PushAct = (pNewX, pNewY) =>
                {
                    int NewHash = GetHash(pNewX, pNewY);
                    if (mTreeDict.ContainsKey(NewHash)) return;
                    if (mXYSet.Contains(NewHash) == false) return;

                    mTreeDict[NewHash] = RootHash;

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

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

    // ハッシュ値を返す
    static int GetHash(int pX, int pY)
    {
        return pX * 10000 + pY;
    }
}

解説

DFSで連結成分分解してます。