迷路をグラフで解くということ

DouKaku?から

再帰の問題例としての迷路問題。（中略）上記のプログラムを作成してください。（再帰を用いた迷路探索問題）

再帰のない言語やあっても深さの制限が厳しい言語があるので、手法は限定しないほうがいいでしょう（構造体とかリストとかも）。これはDouKaku?のすべてのトピックについて言えることですが、この問題が特に異常なのは、学校の宿題を人にやらせようとしているからでしょうか（参考：C/C++の宿題を片付けます 56代目）

私は宿題はどうでもいいので、なるべく楽な解決を目指します

例えばグラフアルゴリズムを標準サポートしている処理系（含Mathematica）なら、最短経路も特に難しいということはないでしょう（愚直なエージェントを実装したいということがあるかもしれませんが）

必要なパッケージをロードします

<<DiscreteMath`GraphPlot`;
<<DiscreteMath`Combinatorica`;

迷路を定義し、データ構造を整えます

• num: 座標を数字に変換する補助関数
• pos: 数字を座標に変換する補助関数

tmp={
      "******",
      "*8000*",
      "****0*",
      "**000*",
      "*90*0*",
      "******"};
maze=Characters/@tmp;
n=Length@First@maze;
num[i_,j_]:=n (i-1)+j
pos[x_]:={Quotient[x,n,1]+1,Mod[x,n,1]}

与えられたデータをグラフのエッジのリストに変換します

start=num@@First@Position[maze,"8"];
goal=num@@First@Position[maze,"9"];
arcs={};
Do[
    If[maze[[i,j]]!="*",
      If[maze[[i,j+1]]!="*",
        AppendTo[arcs,{num[i,j],num[i,j+1]}]];
      If[maze[[i+1,j]]!="*",
        AppendTo[arcs,{num[i,j],num[i+1,j]}]]],
    {i,1,Length@maze-1},{j,1,n-1}];

エッジのリストからグラフを生成し、最短経路アルゴリズムを適用します

sol=ShortestPath[FromUnorderedPairs@arcs,start,goal];
If[Head@sol===ShortestPath || Length@sol==1,False,
  pos/@sol]

{{2,2},{2,3},{2,4},{2,5},{3,5},{4,5},{4,4},{4,3},{5,3},{5,2}}

おまけ：変換した結果のグラフを描画すると下のようになります

GraphPlot[FromUnorderedPairs@arcs,VertexStyleFunction->>Automatic];