人材獲得作戦・４の迷路の最短経路を C# でやってみました

人材獲得作戦・４　試験問題ほか の迷路の最短経路を求める問題を、C# でチャレンジしてみました。

maze.cs

// 人材獲得作戦・４　試験問題ほか
// http://okajima.air-nifty.com/b/2010/01/post-abc6.html

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

// 経路探索の各ステップを表すデータ
class Node {
    public int R { get; private set; }
    public int C { get; private set; }
    public int Step { get; private set; }
    public Node(int r, int c, int step) {
        R = r;
        C = c;
        Step = step;
    }
}

class Program {   
    // 上下左右に進む
    static IEnumerable<Node> Nexts(Node node, int deltaStep) {
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (Math.Abs(i) + Math.Abs(j) == 1) {
                    yield return new Node(node.R + i, node.C + j, node.Step + deltaStep);
                }
            }
        }
    }
    
    static void BFS(List<char[]> g) {
        const char START = 'S';
        const char GOAL  = 'G';
        const char WALL  = '*';
        const char PATH  = '$';

        int rows = g.Count;
        int cols = g[0].Length;
        var q = new Queue<Node>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (g[i][j] == START) {
                    q.Enqueue(new Node(i, j, 1));
                }
            }
        }

        Func<Node, bool> IsOutOfRange = (Node n) => !(0 <= n.R && n.R < rows && 0 <= n.C && n.C < cols);
        int[,] path = new int[rows, cols];
        while (q.Count > 0) {
            var node = q.Dequeue();

            if (IsOutOfRange(node))        continue;
            if (g[node.R][node.C] == WALL) continue;
            if (path[node.R, node.C] > 0)  continue; // 訪問済み
            path[node.R, node.C] = node.Step;

            // ゴールに到達した
            if (g[node.R][node.C] == GOAL) {
                // 経路復元
                var cur = node;
                while (cur.Step > 2) {
                    foreach (var next in Nexts(cur, -1)) {
                        if (IsOutOfRange(next)) continue;

                        if (path[next.R, next.C] == next.Step) {
                            g[next.R][next.C] = PATH;
                            cur = next;
                            break;
                        }
                    }
                }

                foreach (var cs in g) {
                    Console.WriteLine(string.Join("", cs));
                }
                break;
            }

            foreach (var next in Nexts(node, 1)) {
                q.Enqueue(next);
            }
        }
    }
    
    static void Main() {
        var g = new List<char[]>();
        foreach (var s in File.ReadAllText("maze.txt").Trim().Split(new char[] { '\n' })) {
            g.Add(s.ToCharArray());
        }        
        BFS(g);
    }
}

実行結果です。

$ mcs maze.cs
$ mono maze.exe
**************************
*S* *$$$$$               *
*$* *$ * $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

疑問

• 上の URL の「Lv3 最短性のチェック」とは、具体的に何をチェックすればよいのか分かりませんでした。幅優先探索のアルゴリズムを使っているので、目的地が見つかれば、それが最短になりますよね。