[ABC007] C – 幅優先探索（迷路の探索）

Tweet

Pocket

AtCoder Beginner Contest（ABC）から幅優先探索を使って迷路の最短距離を計算する問題です。幅優先探索のチュートリアルのような問題で、誘導に従って解いていけば必ず理解できるとても良い問題です。C#でのコードを書いていきます。

問題文

長いので最初だけ。問題文自体にとても良い解説がついています。図が充実していて非常にわかりやすいのでぜひ見てください。

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

まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。幅優先探索というのは以下の手法です。
（以下略）

https://beta.atcoder.jp/contests/abc007/tasks/abc007_3

ポイント

「Queueを使うのはわかった。でもQueueをどう使うの？」というのがポイント。大まかに言って次のような流れです。C#の場合なので、C++とかはまた違うかもしれません。

1. セル単位のインスタンスに変換して初期設定。例えばCellクラスとする。
2. 調べるマスのQueueをQueue<Cell>で定義する
3. スタートマスをキューに放り込む
4. キューからセルを読み込み、行ける近傍のマスを調べる。動いた距離を記録しつつゴールに到達したら終了

迷路探索アルゴリズムって難しそうに見えますがこれだけです。自分も「こんなんでいいんだ」ってびっくりしました。

まずクラスのほう。迷路の状態を複数の配列で定義するよりセル単位で1個のクラス作っちゃったほうがいいと思います。

    public class Cell
    {
        public int X { get; set; }
        public int Y { get; set; }
        public string CellType { get; set; }
        public int Step { get; set; }

        public static Cell[] GetCells(char[] row, int y)
        {
            var cells = Enumerable.Range(0, row.Length).Select(x => new Cell
            {
                X = x+1,
                Y = y,
                CellType = Convert.ToString(row[x]),
                Step = -1,
            });
            return cells.ToArray();
        }

    }

X, Yは座標です。配列のインデックスは0から始まるのに、問題の迷路の座標は1から始まっているので若干ややこしいことになっていますが、問題関係ない普通の迷路だったら左上の座標を0,0で定義したほうがバグが少ないと思います。

Stepはスタートからの距離を順次記録していくプロパティです。初期値としてとりあえず-1を代入しています。

CellTypeは壁か通路かを示すプロパティ。問題文の通り”#”なら壁、”.”なら通路を表します。

次に迷路の探索の本体です。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var R = vals[0];
            var C = vals[1];

            vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var start = new Tuple<int, int>(vals[0], vals[1]);
            vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var goal = new Tuple<int, int>(vals[0], vals[1]);

            var maze = new Cell[R][];
            foreach(var i in Enumerable.Range(0, R))
            {
                maze[i] = Cell.GetCells(Console.ReadLine().ToCharArray(), i+1);
            }

            //スタートを追加
            var queue = new Queue<Cell>();
            var startCell = maze[start.Item1-1][start.Item2-1];
            startCell.Step = 0;
            queue.Enqueue(startCell);

            while(queue.Count > 0)
            {
                var cell = queue.Dequeue();

                var nextTarget = new Tuple<int, int>[]
                {
                    new Tuple<int, int>(cell.Y-1, cell.X),
                    new Tuple<int, int>(cell.Y+1, cell.X),
                    new Tuple<int, int>(cell.Y, cell.X-1),
                    new Tuple<int, int>(cell.Y, cell.X+1),
                }.Where(x => x.Item1 >= 1 && x.Item1 <= R && x.Item2 >= 1 && x.Item2 <= C)
                .Select(x => maze[x.Item1-1][x.Item2-1])
                .Where(x => x.CellType == "." && x.Step < 0);//未訪問＋通れるマス

                foreach(var nextCell in nextTarget)
                {
                    nextCell.Step = cell.Step + 1;
                    queue.Enqueue(nextCell);

                    if(nextCell.Y == goal.Item1 && nextCell.X == goal.Item2)
                    {
                        Console.WriteLine(nextCell.Step);
                        return;
                    }
                }
            }
        }
    }
}

初期設定あたりは特にいいですよね。座標が1から始まるのがややこしいのでそこだけご注意を。ポイントはwhile～の中だと思います。まずはDequeueで取り出します。これは起点となるマスです。

次はそこから行けるマス（上下左右）を選択します。とりあえず上下左右ピックアップして、IndexOutOfRangeにならないようにフィルタリング、通行可能かつ未到達のマスのみピックアップします。これは一本のLINQで書けるので、自分はこう書いたほうがわかりやすいと思います。

あとは行けるマスをQueueに突っ込み直し、ゴールに到達したら終わりですね。これだけです。

一見複雑なように見える迷路アルゴリズムも、幅優先探索を使うことでかなり簡潔に解くことができました。良い問題なのでぜひ自分で一度解いてみてください。

Tweet

Pocket