8-29 ライツアウト

問題

ライツアウトを解きます。

1問目
■■□■■
■□□□■
□□□□□
■□□□■
■■□■■

2問目
□■■■□
■□□□■
■□□□■
■□□□■
□■■■□

3問目
■□□■■
■□□□□
□■■□■
■□■□■
■■■■□

ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int[,] MasuArr;
        internal List<int[,]> MasuArrLog;
        internal List<string> OpeLog;
    }

    static int[,] MakeQuestion()
    {
        //1問目
        int[,] Question1 = {{1,1,0,1,1},
                            {1,0,0,0,1},
                            {0,0,0,0,0},
                            {1,0,0,0,1},
                            {1,1,0,1,1}};

        //2問目
        int[,] Question2 = {{0,1,1,1,0},
                            {1,0,0,0,1},
                            {1,0,0,0,1},
                            {1,0,0,0,1},
                            {0,1,1,1,0}};

        //3問目
        int[,] Question3 = {{1,0,0,1,1},
                            {1,0,0,0,0},
                            {0,1,1,0,1},
                            {1,0,1,0,1},
                            {1,1,1,1,0}};

        int[,] WKArr = Question3;

        //X座標とY座標の入替
        int[,] WillReturn = (int[,])WKArr.Clone();
        for (int I = 0; I <= WKArr.GetUpperBound(0); I++) {
            for (int J = 0; J <= WKArr.GetUpperBound(1); J++) {
                WillReturn[J, I] = WKArr[I, J];
            }
        }
        return WillReturn;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrY = WillPush.CurrX = 0;
        WillPush.MasuArr = MakeQuestion();
        WillPush.MasuArrLog = new List<int[,]>() { WillPush.MasuArr };
        WillPush.OpeLog = new List<string>() { "初期表示" };
        stk.Push(WillPush);

        var AnswerJyoutaiList = new List<JyoutaiDef>();

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

            if (IsOK(Popped.MasuArr)) {
                AnswerJyoutaiList.Add(Popped);
                continue;
            }

            if (Popped.CurrY == Popped.MasuArr.GetUpperBound(1) + 1) {
                continue;
            }

            //次の座標を設定
            WillPush.CurrY = Popped.CurrY;
            WillPush.CurrX = Popped.CurrX + 1;
            if (WillPush.CurrX == Popped.MasuArr.GetUpperBound(0) + 1) {
                WillPush.CurrY++;
                WillPush.CurrX = 0;
            }

            bool WillPushHanten = false; //反転させるケース
            bool WillPushNonHanten = false; //反転させないケース

            if (Popped.CurrY == 0) { //Y座標が0の場合
                WillPushHanten = true;
                WillPushNonHanten = true;
            }
            else { //Y座標が1以上の場合
                WillPushHanten = (Popped.MasuArr[Popped.CurrX, Popped.CurrY - 1] == 1);
                WillPushNonHanten = !(WillPushHanten);
            }

            if (WillPushHanten) { //反転させるケースをPush
                WillPush.MasuArr = (int[,])Popped.MasuArr.Clone();
                HantenSyori(Popped.CurrX, Popped.CurrY, WillPush.MasuArr);
                WillPush.MasuArrLog = new List<int[,]>(Popped.MasuArrLog) { WillPush.MasuArr };
                WillPush.OpeLog = new List<string>(Popped.OpeLog);
                WillPush.OpeLog.Add(string.Format("マス[{0},{1}]を押下", Popped.CurrX, Popped.CurrY));
                stk.Push(WillPush);
            }

            if (WillPushNonHanten) { //反転させないケースをPush
                WillPush.MasuArr = Popped.MasuArr;
                WillPush.MasuArrLog = Popped.MasuArrLog;
                WillPush.OpeLog = Popped.OpeLog;
                stk.Push(WillPush);
            }
        }

        //最少手数の解のみを出力
        int AnswerCnt = 0;
        int MinLevel = AnswerJyoutaiList.Min(X => X.OpeLog.Count);
        foreach (JyoutaiDef EachJyoutai in AnswerJyoutaiList.Where(X => X.OpeLog.Count == MinLevel)) {
            Console.WriteLine("解{0,2}", ++AnswerCnt);
            OutLog(EachJyoutai.MasuArrLog, EachJyoutai.OpeLog);
        }
    }

    //終了判定
    static bool IsOK(int[,] pMasuArr)
    {
        foreach (int EachInt in pMasuArr) {
            if (EachInt == 1) return false;
        }
        return true;
    }

    //押したマスと周囲4マスの、座標を反転
    static void HantenSyori(int pX, int pY, int[,] pMasuArr)
    {
        MasuHanten(ref pMasuArr[pX, pY]);
        if (pX >= 1) MasuHanten(ref pMasuArr[pX - 1, pY]);
        if (pY >= 1) MasuHanten(ref pMasuArr[pX, pY - 1]);
        if (pX <= pMasuArr.GetUpperBound(0) - 1) MasuHanten(ref pMasuArr[pX + 1, pY]);
        if (pY <= pMasuArr.GetUpperBound(1) - 1) MasuHanten(ref pMasuArr[pX, pY + 1]);
    }

    //0と1の反転
    static void MasuHanten(ref int pVal)
    {
        pVal = (pVal == 0 ? 1 : 0);
    }

    //操作ログの出力
    static void OutLog(List<int[,]> pMasuArrLog, List<string> pOpeLog)
    {
        for (int I = 0; I <= pMasuArrLog.Count - 1; I++) {
            Console.WriteLine("Level{0} {1}", I + 1, pOpeLog[I]);
            for (int Y = 0; Y <= pMasuArrLog[I].GetUpperBound(1); Y++) {
                Console.Write("Y={0}の行 ", Y);
                for (int X = 0; X <= pMasuArrLog[I].GetUpperBound(0); X++) {
                    Console.Write("{0},", pMasuArrLog[I][X, Y]);
                }
                Console.WriteLine();
            }
        }
    }
}

実行結果

解 1
Level1 初期表示
Y=0の行 1,0,0,1,1,
Y=1の行 1,0,0,0,0,
Y=2の行 0,1,1,0,1,
Y=3の行 1,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level2 マス[0,0]を押下
Y=0の行 0,1,0,1,1,
Y=1の行 0,0,0,0,0,
Y=2の行 0,1,1,0,1,
Y=3の行 1,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level3 マス[3,0]を押下
Y=0の行 0,1,1,0,0,
Y=1の行 0,0,0,1,0,
Y=2の行 0,1,1,0,1,
Y=3の行 1,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level4 マス[1,1]を押下
Y=0の行 0,0,1,0,0,
Y=1の行 1,1,1,1,0,
Y=2の行 0,0,1,0,1,
Y=3の行 1,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level5 マス[2,1]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 1,0,0,0,0,
Y=2の行 0,0,0,0,1,
Y=3の行 1,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level6 マス[0,2]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 0,0,0,0,0,
Y=2の行 1,1,0,0,1,
Y=3の行 0,0,1,0,1,
Y=4の行 1,1,1,1,0,
Level7 マス[0,3]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 0,0,0,0,0,
Y=2の行 0,1,0,0,1,
Y=3の行 1,1,1,0,1,
Y=4の行 0,1,1,1,0,
Level8 マス[1,3]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 0,0,0,0,0,
Y=2の行 0,0,0,0,1,
Y=3の行 0,0,0,0,1,
Y=4の行 0,0,1,1,0,
Level9 マス[4,3]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 0,0,0,0,0,
Y=2の行 0,0,0,0,0,
Y=3の行 0,0,0,1,0,
Y=4の行 0,0,1,1,1,
Level10 マス[3,4]を押下
Y=0の行 0,0,0,0,0,
Y=1の行 0,0,0,0,0,
Y=2の行 0,0,0,0,0,
Y=3の行 0,0,0,0,0,
Y=4の行 0,0,0,0,0,

解説

●ライツアウトでは、押した順番は意味を持たない。
●それぞれのライトは、偶数回押すか奇数回押すかのどちらかである。(0回か1回のどちらかである)
という2つの法則を使って、Y=0の行から深さ優先探索してます。
Yが1以上の行は、Yが1小さい行のランプの有無でボタンの押す押さないが確定します。

Actionデリゲートに渡すラムダ式では、refによる参照指定が使えないようなので、
MasuHantenメソッドを定義してます。