11-10 迷路の探索

問題

ここにピリオド(.)とプラス(+)と改行で構成された入力ファイルがあります。
ピリオドは通れないマス、プラスは通れるマスを表現しています。
上から下へたどり着く道があるかどうかを判定するコードを書いてください。

通り抜けられる例
.+.....
.+.+++.
.+.+.+.
.+++.+.
.....+.

通り抜けられない例
..+...+
++.+++.
.+...++
++++.+.
.+..+.+

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int X, Y;
        internal int Level;
        internal string Path;
    }

    static void Main()
    {
        var Map1 = new string[] { ".+.....", //通り抜けられる例
                                  ".+.+++.",
                                  ".+.+.+.",
                                  ".+++.+.",
                                  ".....+."};

        var Map2 = new string[] { "..+...+", //通り抜けられない例
                                  "++.+++.",
                                  ".+...++",
                                  "++++.+.",
                                  ".+..+.+"};
        string[] Map = Map1;
        var que = new Queue<JyoutaiDef>();

        JyoutaiDef WillEnqueue;
        WillEnqueue.Y = 0;
        WillEnqueue.Level = 1;
        WillEnqueue.Path = "";
        for (int X = 0; X <= Map[0].Length - 1; X++) {
            if (Map[0][X] == '+') {
                WillEnqueue.X = X;
                que.Enqueue(WillEnqueue);
            }
        }

        bool IsExistAnswer = false;
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();

            if (Dequeued.Y == Map.GetUpperBound(0)) {
                Console.WriteLine("下に到着しました。経路は{0}", Dequeued.Path);
                IsExistAnswer = true;
                break;
            }
            if (Map.Length * Map[0].Length < Dequeued.Level) {
                break;
            }

            //左に移動
            if (Dequeued.X != 0 && Map[Dequeued.Y][Dequeued.X - 1] == '+') {
                WillEnqueue.X = Dequeued.X - 1; WillEnqueue.Y = Dequeued.Y;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.Path = Dequeued.Path + "←";
                que.Enqueue(WillEnqueue);
            }
            //右に移動
            if (Dequeued.X != Map[0].Length - 1 && Map[Dequeued.Y][Dequeued.X + 1] == '+') {
                WillEnqueue.X = Dequeued.X + 1; WillEnqueue.Y = Dequeued.Y;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.Path = Dequeued.Path + "→";
                que.Enqueue(WillEnqueue);
            }
            //上に移動
            if (Dequeued.Y != 0 && Map[Dequeued.Y - 1][Dequeued.X] == '+') {
                WillEnqueue.X = Dequeued.X; WillEnqueue.Y = Dequeued.Y - 1;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.Path = Dequeued.Path + "↑";
                que.Enqueue(WillEnqueue);
            }
            //下に移動
            if (Map[Dequeued.Y + 1][Dequeued.X] == '+') {
                WillEnqueue.X = Dequeued.X; WillEnqueue.Y = Dequeued.Y + 1;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.Path = Dequeued.Path + "↓";
                que.Enqueue(WillEnqueue);
            }
        }
        if (IsExistAnswer == false) Console.WriteLine("下に到着できません。");
    }
}

実行結果

下に到着しました。経路は↓↓↓→→↑↑→→↓↓↓

解説

幅優先探索を行ってます。