[LeetCode] 490. 迷宫 PHP版

题目描述:

由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。

给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。

迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

示例:

示例 1:

输入 1: 迷宫由以下二维数组表示

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)

输出: true

解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

 

$maze = [
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [1, 1, 1, 0, 0],
    [0, 1, 0, 0, 1],
    [0, 1, 0, 0, 0]
];


function printMaze($maze){
    for ($i = 0; $i < count($maze); $i++) { 
        for ($j = 0; $j < count($maze[$i]); $j++) { 
            echo $maze[$i][$j]." ";
        }
        echo "
";
    }
}


function walk($maze, $start, $end){
    printMaze($maze);
    // 复制下迷宫, 全部为0, 记录走过的路线
    $steps = [];
    for ($i = 0; $i < count($maze); $i++) { 
        for ($j = 0; $j < count($maze[$i]); $j++) { 
            $steps[$i][$j] = 0;
        }
    }
    // printMaze($steps);

    // 上左下右
    $dirs = [[-1, 0], [0, -1], [1, 0], [0,1]];

    $queue[] = $start;
    $k = 1;
    while (!empty($queue)) {
        $cur = array_pop($queue);

        // 等于出口,提前结束
        if($cur[0] == $end[0] && $cur[1] == $end[1]){
            break;
        }

        for ($z = 0; $z < count($dirs); $z++) { 
            $i = $cur[0] + $dirs[$z][0];
            $j = $cur[1] + $dirs[$z][1];

            // 四个方向挨个相加, 判断有没有超出边界
            if($i < 0 || $i >= count($maze)){
                continue;
            }

            if($j < 0 || $j >= count($maze[0])){
                continue;
            }

            // 撞墙了就跳过
            if($maze[$i][$j] == 1){
                continue;
            }

            // 走过了就不要走了
            if($steps[$i][$j] != 0){
                continue;
            }

            if($i == $start[0] and $j == $start[1]){
                continue;
            }
            // 走过的路线记录下
            $steps[$i][$j] = 2;
            // 把四个方向能走的 全部记录下来
            array_push($queue, [$i, $j]);
        }
    }
    echo "
";
    printMaze($steps);
}
walk($maze, [0, 0], [count($maze) - 1, count($maze[0]) - 1]);
exit;