バックトラックで迷路の全経路を取得 : PHPで実装

Tweet

Pocket

迷路に経路が存在するかを判定するために深さ優先探索がよく使われます。また最短経路を幅優先探索で求めることができます。
今回は迷路の始点から終点までの全経路をバックトラックで求めるサンプルを記載しています。

入力例

3 5
.#..#
.....
.##..

0行0列を始点n-1行m-1列を終点として迷路が与えられます。
.は通行可能、#は通行不可を表します。
上記では3行5列になります。

頂点番号を下記のように採番します。

隣接リスト作成

<?php
class AdjList
{
    /**
     * @param integer $n   行数
     * @param integer $m   列数
     * @param array   $map データ行列
     * @return integer[]
     */
    public static function createList($n, $m, $map)
    {
        $list = [];
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $m; $j++) {
                $list[$i * $m + $j] = [];
                if ($map[$i][$j] === '#') {
                    continue;
                }
                if (isset($map[$i + 1][$j]) && $map[$i + 1][$j] === '.') {
                    array_push($list[$i * $m + $j], ( $i + 1 ) * $m + $j);
                }
                if (isset($map[$i - 1][$j]) && $map[$i - 1][$j] === '.') {
                    array_push($list[$i * $m + $j], ( $i - 1 ) * $m + $j);
                }
                if (isset($map[$i][$j + 1]) && $map[$i][$j + 1] === '.') {
                    array_push($list[$i * $m + $j], $i * $m + $j + 1);
                }
                if (isset($map[$i][$j - 1]) && $map[$i][$j - 1] === '.') {
                    array_push($list[$i * $m + $j], $i * $m + $j - 1);
                }
            }
        }
        return $list;
    }
}

経路取得

<?php
/**
 * 経路探索
 *
 * 頂点0からn-1行, m-1列への全経路を求めます。
 * バックトラックで隣接リストから深さ優先探索で全経路を取得します。
 * 
 */
Class Route
{
    /** @var integer $n 行数 */
    private $n;
    /** @var integer $m 列数 */
    private $m;
    /** @var string[] $visited 訪問済フラグ */
    private $visited = [];
    /** @var integer[] $path 経路 */
    private $path = [];
    /** @var integer[] $paths 全経路 */
    private $paths = [];
    /** @var integer[] adjList 隣接リスト 長さ $n*$m */
    private $adjList = [];

    /**
     * Route コンストラクタ
     *
     * @param integer $n   行数
     * @param integer $m   列数
     * @param array   $list 隣接リスト
     */
    public function __construct($n, $m, $list)
    {
        $this->n   = $n;
        $this->m   = $m;
        $this->adjList = $list;
    }

    /**
     * @param integer $n
     */
    private function setPath($n)
    {
        array_push($this->paths, array_slice($this->path, 0, $n));
    }

    /**
     * @param integer $n 頂点番号
     */
    private function search($n)
    {
        $u = $this->path[$n - 1];
        if ($u === ($this->n * $this->m) - 1) {
            $this->setPath($n);
            return;
        } else {
            foreach ($this->adjList[$u] as $v) {
                if ($v === 0) {
                    continue;
                }
                if (!$this->visited[$v]) {
                    $this->path[$n]    = $v;
                    $this->visited[$v] = true;
                    $this->search($n + 1);
                    $this->visited[$v] = false;
                }
            }
        }
    }

    public function getPaths()
    {
        $this->visited = array_fill(0, $this->n * $this->m, false);
        $this->path[0] = 0;
        $this->visited[0] = true;
        $this->search(1);

        return $this->paths;
    }

}

参考記事
お気楽Ｃ言語プログラミング超入門