Q56 公平に分けられたケーキ

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Solve(4, 4);
        Solve(16, 12);
    }

    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal int Level;
        internal char[,] BanArr;
        internal int MinIndX;
        internal int MinIndY;
        internal int OddSum;
        internal int EvenSum;
        internal int CutLenSum;
    }

    static void Solve(int pM, int pN)
    {
        UB_X = pM - 1; UB_Y = pN - 1;
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                WillPush.BanArr[LoopX, LoopY] = '?';
            }
        }
        WillPush.MinIndX = WillPush.MinIndY = 0;
        WillPush.OddSum = WillPush.EvenSum = 0;
        WillPush.CutLenSum = 0;
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.OddSum + Popped.EvenSum == pM * pN) {
                if (AnswerCutLengthSum > Popped.CutLenSum) {
                    AnswerCutLengthSum = Popped.CutLenSum;
                    Console.WriteLine("切った部分の長さ={0}の解候補を発見", Popped.CutLenSum);
                    PrintAnswer(Popped.BanArr);
                }
                continue;
            }

            //下限値枝切り
            int wkMin = Math.Min(UB_X - Popped.MinIndX + 1, UB_Y - Popped.MinIndY + 1);
            if (AnswerCutLengthSum < Popped.CutLenSum + wkMin)
                continue;

            Action<bool, int, int> PushSyori = (pIsHeikouX, pFromInd, pToInd) =>
            {
                WillPush.Level = Popped.Level + 1;

                int wkFromX, wkToX;
                int wkFromY, wkToY;

                if (pIsHeikouX) { //X軸に平行に切る場合
                    wkFromX = Popped.MinIndX; wkToX = UB_X;
                    wkFromY = pFromInd; wkToY = pToInd;
                    WillPush.MinIndX = Popped.MinIndX;
                    WillPush.MinIndY = pToInd + 1;
                    if ((UB_X - Popped.MinIndX + 1) * (UB_Y - Popped.MinIndY + 1) > 1) {
                        WillPush.CutLenSum = Popped.CutLenSum + UB_X - Popped.MinIndX + 1;
                    }
                    else WillPush.CutLenSum = Popped.CutLenSum;
                }
                else { //Y軸に平行に切る場合
                    wkFromX = pFromInd; wkToX = pToInd;
                    wkFromY = Popped.MinIndY; wkToY = UB_Y;
                    WillPush.MinIndX = pToInd + 1;
                    WillPush.MinIndY = Popped.MinIndY;
                    if ((UB_X - Popped.MinIndX + 1) * (UB_Y - Popped.MinIndY + 1) > 1) {
                        WillPush.CutLenSum = Popped.CutLenSum + UB_Y - Popped.MinIndY + 1;
                    }
                    else WillPush.CutLenSum = Popped.CutLenSum;
                }

                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                int wkSum = 0;
                for (int LoopX = wkFromX; LoopX <= wkToX; LoopX++) {
                    for (int LoopY = wkFromY; LoopY <= wkToY; LoopY++) {
                        WillPush.BanArr[LoopX, LoopY] = DecToStr(WillPush.Level);
                        wkSum++;
                    }
                }

                if (WillPush.Level % 2 == 0) {
                    WillPush.OddSum = Popped.OddSum;
                    WillPush.EvenSum = Popped.EvenSum + wkSum;
                }
                else {
                    WillPush.OddSum = Popped.OddSum + wkSum;
                    WillPush.EvenSum = Popped.EvenSum;
                }

                if (WillEdakiri(pM, pN, WillPush) == false)
                    stk.Push(WillPush);
            };

            //X軸に沿ってカットする経路
            int LimitIndY = Popped.MinIndY + (UB_Y - Popped.MinIndY + 1) / 2 - 1;
            if (LimitIndY < Popped.MinIndY) LimitIndY = Popped.MinIndY;
            for (int LoopY = Popped.MinIndY; LoopY <= LimitIndY; LoopY++) {
                PushSyori(true, Popped.MinIndY, LoopY);
            }

            //Y軸に沿ってカットする経路
            if (UB_X - Popped.MinIndX == UB_Y - Popped.MinIndY) continue;
            int LimitIndX = Popped.MinIndX + (UB_X - Popped.MinIndX + 1) / 2 - 1;
            if (LimitIndX < Popped.MinIndX) LimitIndX = Popped.MinIndX;
            for (int LoopX = Popped.MinIndX; LoopX <= LimitIndX; LoopX++) {
                PushSyori(false, Popped.MinIndX, LoopX);
            }
        }
    }

    static bool WillEdakiri(int pM, int pN, JyoutaiDef pJyoutai)
    {
        int AllCnt = pM * pN;
        int RestCnt = AllCnt - pJyoutai.OddSum - pJyoutai.EvenSum;

        //残り2以上なのに半分食べたら枝切り
        if (RestCnt >= 2) {
            if (pJyoutai.OddSum * 2 >= AllCnt) return true;
            if (pJyoutai.EvenSum * 2 >= AllCnt) return true;
        }
        //半分より多く食べたら枝切り
        if (pJyoutai.OddSum * 2 > AllCnt) return true;
        if (pJyoutai.EvenSum * 2 > AllCnt) return true;
        return false;
    }

    //10進数をchar型に変換
    static char DecToStr(int pInt)
    {
        if (pInt < 10) return (char)((int)'1' + pInt - 1);
        return (char)((int)'A' + pInt - 10);
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略

切った部分の長さ=47の解候補を発見
1111122222222222
1111122222222222
1111122222222222
1111122222222222
1111122222222222
1111122222222222
1111133334444444
1111133334444444
1111133334444444
1111133335556677
1111133335556688
111113333555669A

解説

対称解を排除しつつ、深さ優先探索で解いてます。