广度优先和深度优先搜索

<?php

error_reporting(E_ALL);

ini_set('display_errors','On');

// 一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。

$arr = array(

array(0, 1, 0, 0, 0), // i = 0
array(0, 0, 0, 1, 0), // i = 1
array(0, 1, 1, 0, 0),
array(0, 1, 1, 0, 1),
array(0, 0, 0, 0, 1),
array(0, 1, 0, 0, 0) // i = 5

);

$ii = count($arr);

$jj = count($arr[0]);

echo "广度优先搜索", PHP_EOL;

$map = $map2 = array();

for ($i=0; $i < $ii; $i++) {

for ($j=0; $j < $jj; $j++) { 
    $map2[$i][$j] = 0;
}

}

$map = $map2;

for ($i=0; $i < $ii; $i++) {

for ($j=0; $j < $jj; $j++) { 
    echo sprintf("%2d", $arr[$i][$j]) ." ";
}
echo PHP_EOL;

} echo PHP_EOL;

$ret = travelMap($arr, [0,0], [4,3], $map2);

echo PHP_EOL;

for ($i=0; $i < $ii; $i++) {

for ($j=0; $j < $jj; $j++) { 
    echo sprintf("%2d", $map2[$i][$j]) ." ";
}
echo PHP_EOL;

}

echo PHP_EOL;

// 广度优先搜索 (最优解，最短的路径)

function travelMap($map, $st, $end, &$map2 = array()){

if ($map&& $st&& $end) {
    $list = array($st);
    $map2[$st[1]][$st[0]] = 1;
    do{
        $break = false;
        $pos = array_pop($list);
        // echo PHP_EOL, json_encode($pos), PHP_EOL;
        foreach (array([-1,0], [0,-1], [1,0], [0,1]) as $v) {
            $i = $pos[0] + $v[0];
            $j = $pos[1] + $v[1];
            if (!isset($map[$i][$j])) {
               continue;
            }
            if ($map[$i][$j]) {
               continue;
            }
            $weight = 1; // 权重值 步数、距离等
            $val = $map2[$pos[0]][$pos[1]] + $weight;
            if (isset($map2[$i][$j]) && $map2[$i][$j]>0 && $map2[$i][$j] < $val) {
                continue;
            }
            $map2[$i][$j] = $val;
            if ($i == $end[0] && $j == $end[1]) {
                $break = true;
                break;
            }
            array_unshift($list, [$i, $j]);
        }
        if ($break) {
            break;
        }
    }while($list);
    return true;
}
return false;

}

echo "深度优先",PHP_EOL;

travelMap2($arr,[0,0], [4,3], $map);

for ($i=0; $i < $ii; $i++) { for ($j=0; $j < $jj; $j++) { echo sprintf("%2d", $map[$i][$j]) ." "; } echo PHP_EOL; }

echo PHP_EOL;

// 深度优先

function travelMap2($map, $st, $end, &$map2 = array()){

if ($map && $st && $end && $map2) {
    $stack = array($st);
    $map2[$st[1]][$st[0]] = 1;
    do{
        $break = false;
        $pos = array_pop($stack);
        // echo PHP_EOL, json_encode($pos), PHP_EOL;
        foreach (array([-1,0], [0,-1], [1,0], [0,1]) as $v) {
            $i = $pos[0] + $v[0];
            $j = $pos[1] + $v[1];
            if (!isset($map[$i][$j])) {
               continue;
            }
            if ($map[$i][$j]) {
               continue;
            }
            $weight = 1; 
            $val = $map2[$pos[0]][$pos[1]] + $weight;
            if (isset($map2[$i][$j]) && $map2[$i][$j]>0 && $map2[$i][$j] < $val) {
                continue;
            }
            $map2[$i][$j] = $val;
            if ($i == $end[0] && $j == $end[1]) {
                break;
            }
            array_push($stack, [$i, $j]);
        }

    }while($stack);
    return true;
}
return false;

}