ABC293-C Make Takahashi Happy

問題へのリンク

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("3 3");
            WillReturn.Add("3 2 2");
            WillReturn.Add("2 1 3");
            WillReturn.Add("1 5 4");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10");
            WillReturn.Add("1 2 3 4 5 6 7 8 9 10");
            WillReturn.Add("11 12 13 14 15 16 17 18 19 20");
            WillReturn.Add("21 22 23 24 25 26 27 28 29 30");
            WillReturn.Add("31 32 33 34 35 36 37 38 39 40");
            WillReturn.Add("41 42 43 44 45 46 47 48 49 50");
            WillReturn.Add("51 52 53 54 55 56 57 58 59 60");
            WillReturn.Add("61 62 63 64 65 66 67 68 69 70");
            WillReturn.Add("71 72 73 74 75 76 77 78 79 80");
            WillReturn.Add("81 82 83 84 85 86 87 88 89 90");
            WillReturn.Add("91 92 93 94 95 96 97 98 99 100");
            //48620
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[,] mBanArr;
    static int UB_X;
    static int UB_Y;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mBanArr = CreateBanArr(InputList.Skip(1));
        UB_X = mBanArr.GetUpperBound(0);
        UB_Y = mBanArr.GetUpperBound(1);

        mAppearSet.Add(mBanArr[0, 0]);
        dfs(0, 0);

        Console.WriteLine(Answer);
    }

    static HashSet<int> mAppearSet = new HashSet<int>();
    static long Answer = 0;

    static void dfs(int pX, int pY)
    {
        if (pX == UB_X && pY == UB_Y) {
            Answer++;
            return;
        }

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

            if (mAppearSet.Add(mBanArr[pNewX, pNewY])) {
                dfs(pNewX, pNewY);
                mAppearSet.Remove(mBanArr[pNewX, pNewY]);
            }
        };
        CallAct(pX, pY + 1);
        CallAct(pX + 1, pY);
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

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

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }

}

解説

再帰でDFSしてます。