単純な実装では、インタビューで

Question

、私の面接は私にこの質問をしました前にこの問題を解決していない場合、30分で解決する質問。インターネット上には多くの解決策がありますが、どれも簡単ではないようです。この方法は、この制約を尊重すべきである：それはそれを簡単にするためだけに壁やパス

で構成されるべき迷路（正方形の迷路のN×N）

のサイズを受け入れるべき

• を、アルゴリズムはdoensエントリと出口を設定する必要があります

他の人がこの質問を見つけることができるように、私は解答を投稿します。生成された迷路の

例：単純無作為DFSは、迷路を生成するために使用することができる

. # # . # . . . . . 
. . . . . . # # # . 
# . # # # # . . . . 
. # . . . . # . # . 
. # . # # . # . # . 
. # . # . . # . . # 
. . . # . # . # . . 
. # . # . . . # # . 
# . . . # . # . . . 
. . # . # . . . # . 

Answer 1

。 N×N個のサイズに初期化され、完全な壁の迷路を開始するには、この関数は迷路を通過し、possibileたびパス追加：

function generateMaze(&$maze, $point) { 
    $dirs = [ 
     [0,-1], 
     [1,0], 
     [0,1], 
     [-1,0], 
    ]; 

    shuffle($dirs); 

    foreach($dirs as $dir) { 
     $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]]; 

     if (isGoodPath($maze, $newPoint)) { 
      $maze[$newPoint[0]][$newPoint[1]] = '.'; 
      generateMaze($maze, $newPoint); 
     } 
    } 

    return $maze; 
} 

キーがこの機能isGoodPath()この機能の優れた実装で解決するが、単にチェック新しいパスが迷路の内側に、私たちは壁を取り除くことができる場合であれば（つまり、私たちは二つの平行な隣接する「自由」のパスを持つことができないです）

あなたがここに完全な実装を実行することができます。https://ideone.com/oufifB

25×25迷路：

# . . # . . . # . . . . . # . . . . . . . # . # . 
. # . # # # . . . # # # . . # # . # # # . . . . . 
. # . . . . # . # . . . # . . . # . . . . # . # . 
. . # # # . # . . # . # # # # . . . # # . # . . # 
. # . . # . . # . # . . # . # # # # . . # . # . . 
. . # . # # . # . . # . . . . . . # . # . . . # . 
# . . . . # . . # . . # . # . # # . . . . # # . . 
. . # # . . # . . # . # . # . . . . # # . . # . # 
. # . . # . # . # . . # . . # # . # . . # . # . . 
. . . # . . # . . . # . . # . # . # . # . . . # . 
# # . # . # . # # # . # # . . . . # . # . # # . . 
. . . # . . . . . . . . # . # # # # . . . # # . # 
# # # . . # # # # . # . . . # . . . . # # . . . # 
. . . # # . . . . # # . # . # . # # # # # . # # . 
. # . . . . # # . # . . # . # . . . . # . . # . . 
. . # . # # . . . . # # # . . # # # # . . # # # . 
# . . # . . . # # . . . . # . # . . . . # . # # . 
. # . . # . # . # # . # . . . # . # # # . . . . . 
. . # . . # . . . . # . # # . # . # . . # # . # . 
# . . # . . . # # . # . . . . # . . # . . . . # . 
. . # . . # # . # . . # # . # . # . . # . # # . . 
# . . . # . . . . # . . . # . . # # . # . # . # # 
# # . # . . # . # . # # . # # . . . . # . . . . . 
# . . . # # # . . . # # . . # # . # # . # # # # . 
. . # . . . . . # . . . # . . . . . . . . . . . . 

あなたは単に迷路

の国境まで完全な壁を追加することができます「きれい」迷路をしたい場合