AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC218-C Shapes


問題へのリンク


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

    static void Main()
    {
        List<string> InputList = GetInputList();
        int S = int.Parse(InputList[0]);
        char[,] BanArr1 = CreateBanArr(InputList.Skip(1).Take(S));
        char[,] BanArr2 = CreateBanArr(InputList.Skip(1 + S));

        BanArr1 = ArrSyukusyou(BanArr1);
        BanArr2 = ArrSyukusyou(BanArr2);

        List<char[,]> KaitenArrList = DeriveKaitenArrList(BanArr1);
        bool IsMatch = false;
        foreach (char[,] EachCharArr in KaitenArrList) {
            // 横幅違いはNG
            if (BanArr2.GetUpperBound(0) != EachCharArr.GetUpperBound(0)) {
                continue;
            }
            // 縦幅違いはNG
            if (BanArr2.GetUpperBound(1) != EachCharArr.GetUpperBound(1)) {
                continue;
            }

            if (EachCharArr.Cast<char>().SequenceEqual(BanArr2.Cast<char>())) {
                IsMatch = true;
                break;
            }
        }

        Console.WriteLine(IsMatch ? "Yes" : "No");
    }

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

    // 2次元配列の使用してない部分を縮小して返す
    static char[,] ArrSyukusyou(char[,] pTargetArr)
    {
        int XMin = pTargetArr.GetUpperBound(0), YMin = pTargetArr.GetUpperBound(1);
        int XMax = 0, YMax = 0;

        for (int X = 0; X <= pTargetArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= pTargetArr.GetUpperBound(1); Y++) {
                if (pTargetArr[X, Y] == '.') continue;
                if (XMin > X) XMin = X;
                if (YMin > Y) YMin = Y;
                if (XMax < X) XMax = X;
                if (YMax < Y) YMax = Y;
            }
        }

        char[,] WillReturnArr = new char[XMax - XMin + 1, YMax - YMin + 1];
        for (int X = 0; X <= WillReturnArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= WillReturnArr.GetUpperBound(1); Y++) {
                WillReturnArr[X, Y] = pTargetArr[XMin + X, YMin + Y];
            }
        }

        return WillReturnArr;
    }

    // 配列を引数として、回転させた配列のリストをDistinctして返す
    static List<char[,]> DeriveKaitenArrList(char[,] pBaseArr)
    {
        var KaitenArrList = new List<char[,]>();

        //1個目はそのまま
        //■
        //■■■

        //2個目は1個目を時計回りに90度回転
        //■■
        //■
        //■

        //3個目は2個目を時計回りに90度回転
        //■■■
        //  ■

        //4個目は3個目を時計回りに90度回転
        // ■
        // ■
        //■■

        //5個目は1個目とX軸で線対称
        //■■■
        //■

        //6個目は5個目を時計回りに90度回転
        //■■
        // ■
        // ■

        //7個目は6個目を時計回りに90度回転
        //  ■
        //■■■

        //8個目は7個目を時計回りに90度回転
        //■
        //■
        //■■

        int BaseArrUB_X = pBaseArr.GetUpperBound(0);
        int BaseArrUB_Y = pBaseArr.GetUpperBound(1);

        for (int I = 1; I <= 8; I++) KaitenArrList.Add(null);
        for (int P = 0; P <= 6; P += 2) KaitenArrList[P] = new char[BaseArrUB_X + 1, BaseArrUB_Y + 1];
        for (int P = 1; P <= 7; P += 2) KaitenArrList[P] = new char[BaseArrUB_Y + 1, BaseArrUB_X + 1];

        for (int X = 0; X <= BaseArrUB_X; X++) {
            for (int Y = 0; Y <= BaseArrUB_Y; Y++) {
                char SetVal = pBaseArr[X, Y];
                KaitenArrList[0][X, Y] = SetVal;
                KaitenArrList[1][Y, BaseArrUB_X - X] = SetVal;
                KaitenArrList[2][BaseArrUB_X - X, BaseArrUB_Y - Y] = SetVal;
                KaitenArrList[3][BaseArrUB_Y - Y, X] = SetVal;

                KaitenArrList[4][X, BaseArrUB_Y - Y] = SetVal;
                KaitenArrList[5][BaseArrUB_Y - Y, BaseArrUB_X - X] = SetVal;
                KaitenArrList[6][BaseArrUB_X - X, Y] = SetVal;
                KaitenArrList[7][Y, X] = SetVal;
            }
        }
        KaitenArrList.RemoveAt(4);
        KaitenArrList.RemoveAt(4);
        KaitenArrList.RemoveAt(4);
        KaitenArrList.RemoveAt(4);

        // Distinctする
        for (int I = KaitenArrList.Count - 1; 0 <= I; I--) {

            for (int J = 0; J <= I - 1; J++) {
                if (KaitenArrList[I].GetUpperBound(0) !=
                    KaitenArrList[J].GetUpperBound(0)) continue;
                if (KaitenArrList[I].GetUpperBound(1) !=
                    KaitenArrList[J].GetUpperBound(1)) continue;

                IEnumerable<char> wkEnum1 = KaitenArrList[I].Cast<char>();
                IEnumerable<char> wkEnum2 = KaitenArrList[J].Cast<char>();
                if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;

                KaitenArrList.RemoveAt(I);
                break;
            }
        }
        return KaitenArrList;
    }
}


解説

Yyダブルデッカーを解くのに使った
二次元配列の縮小メソッドと
二次元配列の回転メソッドを使ってます。

C#のサンプル集 13-04 Yyダブルデッカー