square869120コンテスト3 B問題 石落としゲーム

問題へのリンク

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("4 4 2");
            WillReturn.Add("3413");
            WillReturn.Add("4121");
            WillReturn.Add("1424");
            WillReturn.Add("2312");
            //23
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4 2");
            WillReturn.Add("1212");
            WillReturn.Add("2121");
            WillReturn.Add("1212");
            WillReturn.Add("2121");
            //54
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7 7 2");
            WillReturn.Add("8989898");
            WillReturn.Add("9898989");
            WillReturn.Add("8989898");
            WillReturn.Add("9898989");
            WillReturn.Add("8989898");
            WillReturn.Add("9898989");
            WillReturn.Add("8989898");
            //2520
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("17 17 2");
            WillReturn.Add("12345678912345678");
            WillReturn.Add("23456789123456789");
            WillReturn.Add("34567891234567891");
            WillReturn.Add("45678912345678912");
            WillReturn.Add("56789123456789123");
            WillReturn.Add("67891234567891234");
            WillReturn.Add("78912345678912345");
            WillReturn.Add("89123456789123456");
            WillReturn.Add("91234567891234567");
            WillReturn.Add("12345678912345678");
            WillReturn.Add("23456789123456789");
            WillReturn.Add("34567891234567891");
            WillReturn.Add("45678912345678912");
            WillReturn.Add("56789123456789123");
            WillReturn.Add("67891234567891234");
            WillReturn.Add("78912345678912345");
            WillReturn.Add("89123456789123456");
            //2354638
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mK = wkArr[2];

        mBanArr = CreateBanArr(InputList.Skip(1));
        UB_X = mBanArr.GetUpperBound(0);
        UB_Y = mBanArr.GetUpperBound(1);

        // 削除するマスを全探索
        var KouhoList = new List<int>();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                KouhoList.Add(DeriveScore(LoopX, LoopY));
            }
        }
        Console.WriteLine(KouhoList.Max());
    }

    // 削除するマスを引数として、スコアを返す
    static int DeriveScore(int pDeleteX, int pDeleteY)
    {
        int ScoreSum = 0;

        int[,] CurrBanArr = (int[,])mBanArr.Clone();
        ExecDeleteMasu(CurrBanArr, pDeleteX, pDeleteY);
        int Beki2 = 1;
        while (true) {
            int CurrScore = DeriveScore(CurrBanArr, Beki2);
            if (CurrScore == 0) break;
            ScoreSum += CurrScore;
            Beki2 *= 2;
        }
        return ScoreSum;
    }

    struct SeqInfoDef
    {
        internal int X;
        internal int Y;
        internal int Num;
    }

    // 盤面を引数として、加算スコアを求め、下に詰める処理も行う
    static int DeriveScore(int[,] pBanArr, int pBeki2)
    {
        var SeqInfoList = new List<SeqInfoDef>();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            var CurrSeqInfoList = new List<SeqInfoDef>();
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {

                SeqInfoDef WillAdd;
                WillAdd.X = LoopX;
                WillAdd.Y = LoopY;
                WillAdd.Num = pBanArr[LoopX, LoopY];

                // 値が不一致の場合
                if (CurrSeqInfoList.Count > 0 && CurrSeqInfoList.Last().Num != pBanArr[LoopX, LoopY]) {
                    if (CurrSeqInfoList.Count >= mK) {
                        SeqInfoList.AddRange(CurrSeqInfoList);
                    }
                    CurrSeqInfoList.Clear();
                    CurrSeqInfoList.Add(WillAdd);
                    continue;
                }
                CurrSeqInfoList.Add(WillAdd);

                // 最後の場合
                if (LoopX == UB_X) {
                    if (CurrSeqInfoList.Count >= mK) {
                        SeqInfoList.AddRange(CurrSeqInfoList);
                    }
                }
            }
        }

        int Score = pBeki2 * SeqInfoList.Sum(pX => pX.Num);

        foreach (SeqInfoDef EachSeqInfo in SeqInfoList) {
            ExecDeleteMasu(pBanArr, EachSeqInfo.X, EachSeqInfo.Y);
        }
        return Score;
    }

    // 削除するマスを引数として、下に詰める
    static void ExecDeleteMasu(int[,] pBanArr, int pDeleteX, int pDeleteY)
    {
        for (int LoopY = pDeleteY; 0 < LoopY; LoopY--) {
            pBanArr[pDeleteX, LoopY] = pBanArr[pDeleteX, LoopY - 1];
        }
        pBanArr[pDeleteX, 0] = 0;
    }

    ////////////////////////////////////////////////////////////////
    // 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.ToCharArray().Select(pX => pX - '0').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;
    }

    ////////////////////////////////////////////////////////////////
    // 2次元配列(int型)のデバッグ出力
    ////////////////////////////////////////////////////////////////
    static void PrintBan(int[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

解説

ナイーブに実装してます。