A70 Lanterns

問題へのリンク

C#のソース(BFS)

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

    static int mN;
    static int[] mAArr;

    static int AllBitOn;

    static Dictionary<int, int> mBeki2Dict = new Dictionary<int, int>();

    struct XYZInfoDef
    {
        internal int X;
        internal int Y;
        internal int Z;
    }
    static List<XYZInfoDef> mXYZInfoList = new List<XYZInfoDef>();

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];

        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int Omomi = 1;
        for (int I = 1; I <= mN; I++) {
            mBeki2Dict[I] = Omomi;
            Omomi *= 2;
        }
        AllBitOn = mBeki2Dict.Values.Sum();

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.Z = wkArr[2];
            mXYZInfoList.Add(WillAdd);
        }

        ExecBFS();
    }

    struct JyoutaiDef
    {
        internal int CurrVal;
        internal int Level;
    }

    static void ExecBFS()
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnque;
        WillEnque.CurrVal = 0;
        WillEnque.Level = 0;

        for (int I = 0; I <= mAArr.GetUpperBound(0); I++) {
            if (mAArr[I] == 1) {
                WillEnque.CurrVal += mBeki2Dict[I + 1];
            }
        }

        Que.Enqueue(WillEnque);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(WillEnque.CurrVal);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (Dequeued.CurrVal == AllBitOn) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            foreach (XYZInfoDef EachXYZInfo in mXYZInfoList) {
                int NewVal = Dequeued.CurrVal;
                var BitList = new List<int>();
                BitList.Add(mBeki2Dict[EachXYZInfo.X]);
                BitList.Add(mBeki2Dict[EachXYZInfo.Y]);
                BitList.Add(mBeki2Dict[EachXYZInfo.Z]);

                foreach (int EachBit in BitList) {
                    if ((NewVal & EachBit) > 0) {
                        NewVal -= EachBit;
                    }
                    else {
                        NewVal += EachBit;
                    }
                }

                if (VisitedSet.Add(NewVal)) {
                    WillEnque.CurrVal = NewVal;
                    WillEnque.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnque);
                }
            }
        }
        Console.WriteLine(-1);
    }
}

C#のソース(BitDP)

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

    static int mN;
    static int[] mAArr;

    static int AllBitOn;

    static Dictionary<int, int> mBeki2Dict = new Dictionary<int, int>();

    struct XYZInfoDef
    {
        internal int X;
        internal int Y;
        internal int Z;
    }
    static List<XYZInfoDef> mXYZInfoList = new List<XYZInfoDef>();

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];

        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int Omomi = 1;
        for (int I = 1; I <= mN; I++) {
            mBeki2Dict[I] = Omomi;
            Omomi *= 2;
        }
        AllBitOn = mBeki2Dict.Values.Sum();

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            XYZInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.Z = wkArr[2];
            mXYZInfoList.Add(WillAdd);
        }

        // 最小手数[BitSet]なDP表
        int?[] PrevDP = new int?[AllBitOn + 1];
        int FirstVal = 0;
        for (int I = 0; I <= mAArr.GetUpperBound(0); I++) {
            if (mAArr[I] == 1) {
                FirstVal += mBeki2Dict[I + 1];
            }
        }
        PrevDP[FirstVal] = 0;

        foreach (XYZInfoDef EachXYZInfo in mXYZInfoList) {
            int?[] CurrDP = (int?[])PrevDP.Clone();
            for (int I = 0; I <= AllBitOn; I++) {
                if (PrevDP[I].HasValue == false) continue;
                int NewI = I;
                NewI ^= mBeki2Dict[EachXYZInfo.X];
                NewI ^= mBeki2Dict[EachXYZInfo.Y];
                NewI ^= mBeki2Dict[EachXYZInfo.Z];

                int NewVal = PrevDP[I].Value + 1;

                if (CurrDP[NewI].HasValue) {
                    if (CurrDP[NewI].Value <= NewVal) {
                        continue;
                    }
                }
                CurrDP[NewI] = NewVal;
            }
            PrevDP = CurrDP;
        }

        if (PrevDP[AllBitOn].HasValue == false) {
            Console.WriteLine(-1);
        }
        else {
            Console.WriteLine(PrevDP[AllBitOn]);
        }
    }
}

解説

BFSで最短距離を求めてます。
BitDPで解くこともできます。