ABC283-E Don't Isolate Elements

問題へのリンク

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("1 1 0");
            WillReturn.Add("1 0 1");
            WillReturn.Add("1 0 0");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4");
            WillReturn.Add("1 0 0 0");
            WillReturn.Add("0 1 1 1");
            WillReturn.Add("0 0 1 0");
            WillReturn.Add("1 1 0 1");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 3");
            WillReturn.Add("0 1 0");
            WillReturn.Add("0 1 1");
            //-1
        }
        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);

        // コスト[1つ上の反転有無,2つ上の反転有無]
        int?[,] PrevDP = new int?[2, 2];
        PrevDP[0, 0] = 0;

        for (int Y = 0; Y <= UB_Y; Y++) {
            int?[,] CurrDP = new int?[2, 2];

            for (int I = 0; I <= 1; I++) {
                for (int J = 0; J <= 1; J++) {
                    if (PrevDP[I, J].HasValue == false) continue;

                    Action<bool> UpdateAct = (pIsRev) =>
                    {
                        var RevYSet = new HashSet<int>();
                        if (pIsRev) RevYSet.Add(Y);
                        if (I == 1) RevYSet.Add(Y - 1);
                        if (J == 1) RevYSet.Add(Y - 2);

                        // 2行目以降の場合
                        if (Y > 0) {
                            if (HasIsolateElement(Y - 1, RevYSet)) return;
                        }

                        // 最終行の場合
                        if (Y == UB_Y && HasIsolateElement(Y, RevYSet)) return;

                        int NewVal = PrevDP[I, J].Value;
                        if (pIsRev) NewVal++;

                        int NewI = pIsRev ? 1 : 0;
                        int NewJ = I;

                        if (CurrDP[NewI, NewJ].HasValue) {
                            if (CurrDP[NewI, NewJ].Value <= NewVal) {
                                return;
                            }
                        }
                        CurrDP[NewI, NewJ] = NewVal;
                    };

                    // この行を反転する場合
                    UpdateAct(true);

                    // この行を反転しない場合
                    UpdateAct(false);
                }
            }
            PrevDP = CurrDP;
        }

        var AnswerList = new List<int>();
        for (int I = 0; I <= 1; I++) {
            for (int J = 0; J <= 1; J++) {
                if (PrevDP[I, J].HasValue) {
                    AnswerList.Add(PrevDP[I, J].Value);
                }
            }
        }
        if (AnswerList.Count == 0) {
            Console.WriteLine(-1);
        }
        else {
            Console.WriteLine(AnswerList.Min());
        }
    }

    static bool HasIsolateElement(int pBaseY, HashSet<int> pRevYSet)
    {
        for (int X = 0; X <= UB_X; X++) {
            int CurrVal = mBanArr[X, pBaseY];
            if (pRevYSet.Contains(pBaseY)) {
                CurrVal = 1 - CurrVal;
            }

            var OtherValList = new List<int>();
            if (0 <= X - 1) {
                int AddVal = mBanArr[X - 1, pBaseY];
                if (pRevYSet.Contains(pBaseY)) {
                    AddVal = 1 - AddVal;
                }
                OtherValList.Add(AddVal);
            }
            if (X + 1 <= UB_X) {
                int AddVal = mBanArr[X + 1, pBaseY];
                if (pRevYSet.Contains(pBaseY)) {
                    AddVal = 1 - AddVal;
                }
                OtherValList.Add(AddVal);
            }

            if (0 <= pBaseY - 1) {
                int AddVal = mBanArr[X, pBaseY - 1];
                if (pRevYSet.Contains(pBaseY - 1)) {
                    AddVal = 1 - AddVal;
                }
                OtherValList.Add(AddVal);
            }

            if (pBaseY + 1 <= UB_Y) {
                int AddVal = mBanArr[X, pBaseY + 1];
                if (pRevYSet.Contains(pBaseY + 1)) {
                    AddVal = 1 - AddVal;
                }
                OtherValList.Add(AddVal);
            }

            if (OtherValList.TrueForAll(pX => pX != CurrVal)) {
                return true;
            }
        }
        return false;
    }

    ////////////////////////////////////////////////////////////////
    // 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;
    }
}

解説

上の行から順に反転有無を決めていくとして
コスト[1つ上の反転有無,2つ上の反転有無]
でDPしてます。

反転有無を決めた行の、1つ上の行にIsolateElementがあったら枝切りできます。