题解 | #迷宫问题#

<?php
[$m, $n] = explode(' ', trim(fgets(STDIN)));

$arr = [];
for($i=0; $i<$m; $i++) {
    $arr[] = explode(' ', trim(fgets(STDIN)));
}

$routeArr = [[0, 0]];
$routeAllArr = [];
$arr[0][0] = 1;
$endX = $m-1;
$endY = $n-1;
// fds(0, 0, $m-1, $n-1, $arr, $routeArr, $routeAllArr);
fdsOne(0, 0, $endX, $endY, $arr, $routeArr);
echo '所有可能的路线：';
print_r($routeAllArr);
// print_r($routeArr);

/**
 * 找到一条路线就终止
 */
function fdsOne($x, $y, &$endX, &$endY, &$arr, &$routeArr) {
    // 如果当前点是终点，直接返回
    if ($endX == $x && $endY == $y) {
        foreach ($routeArr as $item) {
            echo "({$item[0]},$item[1])".PHP_EOL;
        }
        exit;
    }

    $dx = [0, 0, -1, 1];
    $dy = [1, -1, 0, 0];
    for ($i=0; $i<4; $i++) {
        $xTmp = $x + $dx[$i];
        $yTmp = $y + $dy[$i];
        // 只有终点刚好是边界点才能这样，如果不是则需要另外传边界点
        // if ($xTmp>=0 && $xTmp<=$endX && $yTmp>=0 && $yTmp<=$endY && 
        //     $arr[$xTmp][$yTmp] == 0
        // ) {
        //     $arr[$xTmp][$xTmp] = 1;
        //     $routeArr[] = [$xTmp, $yTmp];
        //     fdsOne($xTmp, $yTmp, $endX, $endY, $arr, $routeArr);
        //     array_pop($routeArr);
        //     $arr[$xTmp][$xTmp] = 0;
        // }
        // $memory = memory_get_peak_usage()/1024/1024;
        // echo '内存：'.$memory;
        if (isset($arr[$xTmp][$yTmp]) && $arr[$xTmp][$yTmp] == 0) {
            // echo "({$xTmp}, $yTmp)".PHP_EOL;
            $arr[$xTmp][$yTmp] = 1;
            $routeArr[] = [$xTmp, $yTmp];
            fdsOne($xTmp, $yTmp, $endX, $endY, $arr, $routeArr);
            array_pop($routeArr);
            $arr[$xTmp][$xTmp] = 0;
        }
    }
    return;
}

/**
 * 记录所有路线，最后遍历选择找到最短路线
 */
function fds($x, $y, $endX, $endY, &$arr, &$routeArr, &$routeAllArr) {
    // 如果当前点是终点，直接返回
    if ($endX == $x && $endY == $y) {
        $routeAllArr[] = $routeArr;
        return;
    }

    $dx = [0, 0, -1, 1];
    $dy = [1, -1, 0, 0];
    for ($i=0; $i<4; $i++) {
        $xTmp = $x + $dx[$i];
        $yTmp = $y + $dy[$i];
        // 只有终点刚好是边界点才能这样，如果不是则需要另外传边界点
        if ($xTmp>=0 && $xTmp<=$endX && $yTmp>=0 && $yTmp<=$endY && 
            $arr[$xTmp][$yTmp] == 0
        ) {
            $arr[$xTmp][$yTmp] = 1;
            $routeArr[] = [$xTmp, $yTmp];
            fds($xTmp, $yTmp, $endX, $endY, $arr, $routeArr, $routeAllArr);
            array_pop($routeArr);
            $arr[$xTmp][$xTmp] = 0;
        }
    }
    return;
}

封装了两种方法，一种获取到路径就停止，一种获取所有能走通的路径。