<?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;
}
有疑问加站长微信联系（非本文作者））
