C# で迷路を解いてみた。あとアルゴリズムの解説
人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。
ということで、迷路を解いてみました。プログラミングには約40分。構想時間を含めても3時間以内には解けるはず。命名は適当すぎてリファクタリングするきにもならない出来だけど。
using System; using System.Collections.Generic; using System.Drawing; using System.Text; using System.Text.RegularExpressions; using System.IO; class Program { static void Main(string[] args) { Maze maze = Maze.LoadFromFile(args[0]); DateTime before = DateTime.Now; maze.resolve(); Console.WriteLine("resolve - {0} ms", (DateTime.Now - before).TotalMilliseconds); Console.WriteLine(maze); } class Maze { public Point start = Point.Empty; public Point goal = Point.Empty; public bool[,] wall; public bool[,] path; public static Maze LoadFromFile(String filename) { Maze result = new Maze(); string[] line; using (StreamReader sr = new StreamReader(filename)) { line = Regex.Split(sr.ReadToEnd(), "\r\n|\r|\n"); } result.wall = new bool[line[0].Length, line.Length]; result.path = new bool[line[0].Length, line.Length]; for (int y = 0; y < line.Length; y++) { for (int x = 0; x < line[y].Length; x++) { switch (line[y][x]) { case '*': result.wall[x, y] = true; break; case 'S': result.start = new Point(x, y); break; case 'G': result.goal = new Point(x, y); break; } } } return result; } public void resolve() { bool[,] wall2 = (bool[,]) wall.Clone(); Point[] move = { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; Queue<Location> queue = new Queue<Location>(); queue.Enqueue(new Location(start, 0, null)); wall2[start.X, start.Y] = true; while (0 < queue.Count) { Location location = queue.Dequeue(); if (location.here == goal) { while (location != null) { path[location.here.X, location.here.Y] = true; location = location.before; } break; } else { for (int i = 0; i < move.Length; i++) { Point next = location.here; next.Offset(move[i]); if (!wall2[next.X, next.Y]) { queue.Enqueue(new Location(next, location.distance + 1, location)); wall2[next.X, next.Y] = true; } } } } } private class Location { public Point here = Point.Empty; public int distance; public Location before; public Location(Point here, int distance, Location before) { this.here = here; this.distance = distance; this.before = before; } } public override string ToString() { StringWriter sw = new StringWriter(); for (int y = 0; y < wall.GetLength(1); y++) { for (int x = 0; x < wall.GetLength(0); x++) { if (x == start.X && y == start.Y) sw.Write('S'); else if (x == goal.X && y == goal.Y) sw.Write('G'); else if (path[x, y]) sw.Write('$'); else if (wall[x, y]) sw.Write('*'); else sw.Write(' '); } sw.WriteLine(); } return sw.ToString(); } } }
今回の問題のポイントなんだけど、まずいろんな人が思いついている「ダイクストラ法」について突っ込ませてもらいたい。ダイクストラ法は「重み付きグラフにおける最短経路問題」を扱ったアルゴリズムなので、今回の問題のような「重み無しグラフにおける最短経路問題」では、ちょっと余分な処理が混じることになる。ダイクストラ法のキモは「短い道からたどれば”急がば回れ”の場所を見つけられるよね」という流れなんだけど、今回の問題ではもっと距離の概念が単純なんだよね。*1
結局、今回の問題では塗りつぶしのアルゴリズムで十分という結果になってしまう。距離 n の点の周囲は距離 n + 1 の点だから、距離 0 のスタートから初めて色塗りしながら徐々に距離を増やしていき、最初にゴールにたどり着いた奴を逆に辿れば、それが最短経路になる。
queue に入っている点の距離が全て n ならば、次に queue に追加されるのは距離 n + 1 の点。距離 n の点が全て無くなれば、次は queue の中身は距離 n + 1 の点だけになる。最初に追加されるのは距離 0 であるスタート地点。よって queue から取り出される点は、全てスタート地点からの最短距離を辿っている。ゴールが queue から取り出されれば、それは最短距離を辿った経路情報を持っていることになる。よって、このプログラムは最短経路を出力する。
……はず。間違ってたらそれはそれで恥ずかしいな。
ちなみにこの手法では、迷路上の全ての点を塗りおわった時点で終了するから、迷路の縦を M、横を N とすると O(MN) になっていると思います。
