ABC375-C Spiral Rotation

問題へのリンク

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("8");
            WillReturn.Add(".......#");
            WillReturn.Add(".......#");
            WillReturn.Add(".####..#");
            WillReturn.Add(".####..#");
            WillReturn.Add(".##....#");
            WillReturn.Add(".##....#");
            WillReturn.Add(".#######");
            WillReturn.Add(".#######");
            //........
            //#######.
            //#.....#.
            //#.###.#.
            //#.#...#.
            //#.#####.
            //#.......
            //########
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add(".#.#.#");
            WillReturn.Add("##.#..");
            WillReturn.Add("...###");
            WillReturn.Add("###...");
            WillReturn.Add("..#.##");
            WillReturn.Add("#.#.#.");
            //#.#.#.
            //.#.#.#
            //#.#.#.
            //.#.#.#
            //#.#.#.
            //.#.#.#
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("12");
            WillReturn.Add(".......#.###");
            WillReturn.Add("#...#...#..#");
            WillReturn.Add("###.#..#####");
            WillReturn.Add("..#.#.#.#...");
            WillReturn.Add(".#.....#.###");
            WillReturn.Add(".......#.#..");
            WillReturn.Add("#...#..#....");
            WillReturn.Add("#####.......");
            WillReturn.Add("...#...#.#.#");
            WillReturn.Add("..###..#..##");
            WillReturn.Add("#..#.#.#.#.#");
            WillReturn.Add(".####.......");
            //.#..##...##.
            //#.#.#.#.#...
            //###.##..#...
            //#.#.#.#.#...
            //#.#.##...##.
            //............
            //............
            //.###.###.###
            //...#...#.#..
            //.###...#.###
            //...#...#...#
            //.###...#.###
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = int.Parse(InputList[0]);
        UB = mN - 1;

        int[,] ChangeCntArr = ExecBFS();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                ChangeCntArr[X, Y] %= 4;

                // 周りが逆なので調整
                if (ChangeCntArr[X, Y] == 1) {
                    ChangeCntArr[X, Y] = 3;
                }
                else if (ChangeCntArr[X, Y] == 3) {
                    ChangeCntArr[X, Y] = 1;
                }
            }
        }

        // すり替えで変換
        char[,] PrevAnswerArr = CreateBanArr(InputList.Skip(1));
        for (int I = 1; I <= 3; I++) {
            char[,] CurrAnswerArr = new char[UB + 1, UB + 1];
            for (int Y = 0; Y <= UB; Y++) {
                for (int X = 0; X <= UB; X++) {
                    int ChangeCnt = ChangeCntArr[X, Y];
                    char CurrChar = PrevAnswerArr[X, Y];
                    int AfterX = X;
                    int AfterY = Y;
                    if (ChangeCnt >= I) {
                        ExecChange(ref AfterX, ref AfterY);
                    }
                    CurrAnswerArr[AfterX, AfterY] = CurrChar;
                }
            }
            PrevAnswerArr = CurrAnswerArr;
        }
        PrintBan(PrevAnswerArr);
    }

    // 変換を行う
    static void ExecChange(ref int pX, ref int pY)
    {
        int NewX = pY;
        int NewY = UB - pX;

        pX = NewX;
        pY = NewY;
    }

    // BFSで変換数を設定
    static int[,] ExecBFS()
    {
        int[,] ChangeCntArr = new int[UB + 1, UB + 1];

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;

        // 外周に1を設定
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                if (X == 0 || X == UB || Y == 0 || Y == UB) {
                    ChangeCntArr[X, Y] = 1;

                    WillEnqueue.CurrX = X;
                    WillEnqueue.CurrY = Y;
                    Que.Enqueue(WillEnqueue);
                }
            }
        }

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            int CurrVal = ChangeCntArr[Dequeued.CurrX, Dequeued.CurrY];

            Action<int, int> EnqueueAct = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB < pNewX) return;
                if (pNewY < 0 || UB < pNewY) return;

                if (ChangeCntArr[pNewX, pNewY] > 0) return;
                ChangeCntArr[pNewX, pNewY] = CurrVal + 1;

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                Que.Enqueue(WillEnqueue);
            };

            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY - 1);

            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY);

            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY + 1);
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY + 1);
        }
        return ChangeCntArr;
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
    }

    ////////////////////////////////////////////////////////////////
    // 2次元配列(char型)のデバッグ出力
    ////////////////////////////////////////////////////////////////
    static void PrintBan(char[,] 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());
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

解説

最初にBFSでマス目ごとの変換数を求めます。
11111111
12222221
12333321
12344321
12344321
12333321
12222221
11111111

次に変換関数の周期を考えます。
初期状態 (X,Y)
1回目    (Y,UB-X);
2回目    (UB-X,UB-Y);
3回目    (UB-Y,X);
4回目    (X,Y);
変換関数が、ベクトルの90度回転でもあるので、
周期は4だと分かります。

後は、座標ごとに最大3回の変換を行い、解けます。