こしあん
2018-10-07

[ABC007] C – 幅優先探索(迷路の探索)

Pocket
LINEで送る
Delicious にシェア

1.5k{icon} {views}


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に突っ込み直し、ゴールに到達したら終わりですね。これだけです。

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



Shikoan's ML Blogの中の人が運営しているサークル「じゅ~しぃ~すくりぷと」の本のご案内

技術書コーナー

【新刊】インフィニティNumPy――配列の初期化から、ゲームの戦闘、静止画や動画作成までの221問

「本当の実装力を身につける」ための221本ノック――
機械学習(ML)で避けて通れない数値計算ライブラリ・NumPyを、自在に活用できるようになろう。「できる」ための体系的な理解を目指します。基礎から丁寧に解説し、ディープラーニング(DL)の難しいモデルで遭遇する、NumPyの黒魔術もカバー。初心者から経験者・上級者まで楽しめる一冊です。問題を解き終わったとき、MLやDLなどの発展分野にスムーズに入っていけるでしょう。

本書の大きな特徴として、Pythonの本でありがちな「NumPyとML・DLの結合を外した」点があります。NumPyを理解するのに、MLまで理解するのは負担が大きいです。本書ではあえてこれらの内容を書いていません。行列やテンソルの理解に役立つ「従来の画像処理」をNumPyベースで深く解説・実装していきます。

しかし、問題の多くは、DLの実装で頻出の関数・処理を重点的に取り上げています。経験者なら思わず「あー」となるでしょう。関数丸暗記では自分で実装できません。「覚える関数は最小限、できる内容は無限大」の世界をぜひ体験してみてください。画像編集ソフトの処理をNumPyベースで実装する楽しさがわかるでしょう。※紙の本は電子版の特典つき

モザイク除去から学ぶ 最先端のディープラーニング

「誰もが夢見るモザイク除去」を起点として、機械学習・ディープラーニングの基本をはじめ、GAN(敵対的生成ネットワーク)の基本や発展型、ICCV, CVPR, ECCVといった国際学会の最新論文をカバーしていく本です。
ディープラーニングの研究は発展が目覚ましく、特にGANの発展型は市販の本でほとんどカバーされていない内容です。英語の原著論文を著者がコードに落とし込み、実装を踏まえながら丁寧に解説していきます。
また、本コードは全てTensorFlow2.0(Keras)に対応し、Googleの開発した新しい機械学習向け計算デバイス・TPU(Tensor Processing Unit)をフル活用しています。Google Colaboratoryを用いた環境構築不要の演習問題もあるため、読者自ら手を動かしながら理解を深めていくことができます。

AI、機械学習、ディープラーニングの最新事情、奥深いGANの世界を知りたい方にとってぜひ手にとっていただきたい一冊となっています。持ち運びに便利な電子書籍のDLコードが付属しています。

「おもしろ同人誌バザールオンライン」で紹介されました!(14:03~) https://youtu.be/gaXkTj7T79Y?t=843

まとめURL:https://github.com/koshian2/MosaicDeeplearningBook
A4 全195ページ、カラー12ページ / 2020年3月発行

Shikoan's ML Blog -Vol.1/2-

累計100万PV超の人気ブログが待望の電子化! このブログが電子書籍になって読みやすくなりました!

・1章完結のオムニバス形式
・機械学習の基本からマニアックなネタまで
・どこから読んでもOK
・何巻から読んでもOK

・短いものは2ページ、長いものは20ページ超のものも…
・通勤・通学の短い時間でもすぐ読める!
・読むのに便利な「しおり」機能つき

・全巻はA5サイズでたっぷりの「200ページオーバー」
・1冊にたっぷり30本収録。1本あたり18.3円の圧倒的コストパフォーマンス!
・文庫本感覚でお楽しみください

北海道の駅巡りコーナー

日高本線 車なし全駅巡り

ローカル線や秘境駅、マニアックな駅に興味のある方におすすめ! 2021年に大半区間が廃線になる、北海道の日高本線の全区間・全29駅(苫小牧~様似)を記録した本です。マイカーを使わずに、公共交通機関(バス)と徒歩のみで全駅訪問を行いました。日高本線が延伸する計画のあった、襟裳岬まで様似から足を伸ばしています。代行バスと路線バスの織り成す極限の時刻表ゲームと、絶海の太平洋と馬に囲まれた日高路、日高の隠れたグルメを是非たっぷり堪能してください。A4・フルカラー・192ページのたっぷりのボリュームで、あなたも旅行気分を漫喫できること待ったなし!

見どころ:日高本線被災区間(大狩部、慶能舞川橋梁、清畠~豊郷) / 牧場に囲まれた絵笛駅 / 窓口のあっただるま駅・荻伏駅 / 汐見の戦争遺跡のトーチカ / 新冠温泉、三石温泉 / 襟裳岬

A4 全192ページフルカラー / 2020年11月発行


Pocket
LINEで送る
Delicious にシェア

Tags:, ,

Add a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です