第1回 CodeIQプロコン 3問目 猿

■■■問題■■■

n*n (5 <= n <= 100) の文字列の中から、
「MENMA」と連続する部分があるかどうかを判定してください。



のように一直線に並んでいる場合だけでなく、



や



のように途中で折れ曲がっていても構いません。

■■■入力■■■

標準入力から、n*n (5 <= n <= 100) の文字列が与えられます。
文字列に含まれる文字は「A, E, M, N」のいずれかで、改行コードはLFです。

■■■出力■■■

文字列に連続する「MENMA」が含まれる場合は「yes」、
含まれない場合は「no」を、標準出力に出力してください。
出力にはyes/no以外の文字は出力しないでください。行末の改行については有無を問いません。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("MENME");
            WillReturn.Add("NMENM");
            WillReturn.Add("ENMEN");
            WillReturn.Add("MENMA");
            WillReturn.Add("NMENM");
            //yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("EMNME");
            WillReturn.Add("MNANE");
            WillReturn.Add("EAENN");
            WillReturn.Add("MEEEE");
            WillReturn.Add("EMNEM");
            //no
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB;
    static List<string> InputList;

    static void Main()
    {
        InputList = GetInputList();
        UB = InputList.Count - 1;

        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                char CurrChar = XYChar(X, Y);
                //Aだったら、深さ優先探索を行う
                if (CurrChar != 'A') continue;
                if (ExecDFS(X, Y)) {
                    Console.WriteLine("yes");
                    return;
                }
            }
        }
        Console.WriteLine("no");
    }

    //X座標とY座標を引数として、当該座標の文字を返す
    static char XYChar(int pX, int pY)
    {
        return InputList[pY][pX];
    }

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

    //深さ優先探索を行ってMENMAかを返す
    static bool ExecDFS(int pX, int pY)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 1;
        WillPush.CurrX = pX;
        WillPush.CurrY = pY;
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.Level == 5) return true;

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

                //MENMAをAから逆探索する
                if (Popped.Level == 1 && XYChar(pNewX, pNewY) != 'M') return;
                if (Popped.Level == 2 && XYChar(pNewX, pNewY) != 'N') return;
                if (Popped.Level == 3 && XYChar(pNewX, pNewY) != 'E') return;
                if (Popped.Level == 4 && XYChar(pNewX, pNewY) != 'M') return;

                WillPush.Level = Popped.Level + 1;
                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                stk.Push(WillPush);
            };

            PushAct(Popped.CurrX, Popped.CurrY - 1);
            PushAct(Popped.CurrX, Popped.CurrY + 1);
            PushAct(Popped.CurrX - 1, Popped.CurrY);
            PushAct(Popped.CurrX + 1, Popped.CurrY);
        }
        return false;
    }
}

解説

計算量を減らすため、Aから逆に探索してます。

『第1回CodeIQ プログラミングコンテスト』問題解説 --- CodeIQ MAGAZINE