ABC-007-C 幅優先探索

■■■問題■■■

たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。
盤面は以下のような形式で与えられます。

●まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
●次に、それぞれのマスが通行可能な空きマス('.')か
  通行不可能な壁マス('#')かという情報を持った盤面が与えられる。
  盤面は壁マスで囲まれている。
  スタート地点とゴール地点は必ず空きマスであり、
  スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。
  具体的には、入出力例を参考にすると良い。

今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。
どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。
幅優先探索というのは以下の手法です。

●スタート地点から近い(たどり着くための最短手数が少ない)マスから順番に、
  たどり着く手数を以下のように確定していく。説明の例として図1の迷路を利用する。

図1. 説明に用いる盤面


●最初に、スタート地点は、スタート地点から手数0でたどり着ける(当然)ので、
  最短手数0で確定させる(図2)。

図2. 最短手数0でたどり着けるマスが確定(初期)


●次に、スタート地点の四近傍(上下左右)の空きマスについて、
  手数1で確定させる(図3)。

図3. 最短手数1でたどり着けるマスが確定


●次に、手数1で確定したそれぞれのマスの4近傍を見て、
  まだ確定していない空きマスがあればそのマスを手数2で確定させる(図4)。

図4. 最短手数2でたどり着けるマスが確定


●次に、手数2で確定したそれぞれのマスの4近傍を見て、
  まだ確定していない空きマスがあればそのマスを手数3で確定させる(図5)。

図5. 最短手数3でたどり着けるマスが確定


●次に、手数3で確定したそれぞれのマスの4近傍を見て、
  まだ確定していない空きマスがあればそのマスを手数4で確定させる(図6)。

図6. 最短手数4でたどり着けるマスが確定


●上記の手順を確定の更新が無くなるまで繰り返すと、
  スタート地点からたどり着ける全ての空きマスについて最短手数が確定する(図7)。
  スタートとゴールは必ず空きマスを辿ってたどり着けるという制約があるので、
  ゴール地点への最短手数も分かる。

図7. すべてのたどり着けるマスへの最短手数が確定


さて、この処理をスマートに実装するためには、
先入れ先出し(FIFO)のキュー(Queue)というデータ構造を用いると良いことが知られています。
もちろん、使わなくても解くことは可能です。
今回、よく分からなければ思いついた方法で解くことをおすすめします。
先入れ先出しのキューとは以下のような機能を持つデータ構造です。

●追加(Push): キューの末尾にデータを追加する。
●取り出し(Pop): キューの先頭のデータを取り出す。

このデータ構造を使うと、
先ほどの幅優先探索の説明における「マスの最短手数の確定」のタイミングで
その確定マスをキューに追加し、追加操作が終わればPopを行い、
取り出したマスの4近傍を調べるということを繰り返せば
(つまり先に追加されたものから順番に処理していけば)、
簡潔に処理ができることが分かります。

■■■入力■■■

R C
sy sx
gy gx
c(1,1)c(1,2) ・・・ c(1,C)
c(2,1)c(2,2) ・・・ c(2,C)
・
・
・
c(R,1)c(R,2) ・・・ c(R,C)

●1行目には、行数 R(1 <= R <= 50)と列数 C(1 <= C <= 50)が
  それぞれ空白区切りで与えられる。
●2行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。
  スタート地点がsy行sx列にあることを意味する。
  1 <= sy <= R　かつ 1 <= sx <= C である。
●3行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。
  ゴール地点がgy行gx列にあることを意味する。
  1 <= gy <= R かつ 1 <= gx <= C であり、
  (gy,gx)≠(sy,sx)であることが保障されている。
●4行目からR行、長さCの文字列が1行ずつ与えられる。
  各文字は'.'もしくは'#'のいずれかであり、
  i回目 (1 <= i <= R) に与えられられる文字列のうち 
  j文字目 (1 <= j <= C) について、
  その文字が '.' なら、マス (i,j) が空きマスであり、
  '#'なら、マス (i,j) が壁マスであることをあらわす。
●盤面は壁マスで囲まれている。
  つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス(i,j)について、c(i,j)は'#'である。
  また、スタート地点とゴール地点は必ず空きマスであり、
  スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。

■■■出力■■■

スタート地点からゴール地点に移動する最小手数を1行に出力せよ。

図8. 入出力例2において最小手数10を達成する進み方

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("7 8");
            WillReturn.Add("2 2");
            WillReturn.Add("4 5");
            WillReturn.Add("########");
            WillReturn.Add("#......#");
            WillReturn.Add("#.######");
            WillReturn.Add("#..#...#");
            WillReturn.Add("#..##..#");
            WillReturn.Add("##.....#");
            WillReturn.Add("########");
            //11
            //問題文中の例です
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 8");
            WillReturn.Add("2 2");
            WillReturn.Add("2 4");
            WillReturn.Add("########");
            WillReturn.Add("#.#....#");
            WillReturn.Add("#.###..#");
            WillReturn.Add("#......#");
            WillReturn.Add("########");
            //10
            //図8のように進めば10手でたどり着くことが進むことができます
            //(※Sはスタート、Gはゴールをあらわす)
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("50 50");
            WillReturn.Add("2 2");
            WillReturn.Add("49 49");
            WillReturn.Add(new string('#', 50));
            for (int I = 1; I <= 48; I++)
                WillReturn.Add('#' + new string('.', 48) + '#');
            WillReturn.Add(new string('#', 50));
            //94
            //もはやただの広い空間であり、
            //迷路と呼んで良いのかは分からないが
            //この問題でこのような盤面も迷路として扱う。
            //兎にも角にも、スタートからゴールへの最短手数は94である。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        int R = wkArr[0], C = wkArr[1];
        SplitAct(InputList[1]);
        int SX = wkArr[1] - 1, SY = wkArr[0] - 1;
        SplitAct(InputList[2]);
        int GX = wkArr[1] - 1, GY = wkArr[0] - 1;

        char[,] CArr = new char[C, R];
        int UB_X = CArr.GetUpperBound(0);
        int UB_Y = CArr.GetUpperBound(1);
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                CArr[X, Y] = InputList[Y + 3][X];
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = SX;
        WillEnqueue.CurrY = SY;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(string.Format("{0},{1}", SX, SY));
        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア判定
            if (Dequeued.CurrX == GX && Dequeued.CurrY == GY) {
                Console.WriteLine(Dequeued.Level);
                break;
            }

            Action<int, int> EnqueSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                if (CArr[pNewX, pNewY] == '#') return;

                if (VisitedSet.Add(string.Format("{0},{1}", pNewX, pNewY))) {
                    WillEnqueue.CurrX = pNewX;
                    WillEnqueue.CurrY = pNewY;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            };
            EnqueSyori(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueSyori(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueSyori(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueSyori(Dequeued.CurrX + 1, Dequeued.CurrY);
        }
    }
}

解説

幅優先探索で解いてます。