当前位置： 面试刷题>> 逃离幽灵 (经典算法题500道)

题目描述补充

逃离幽灵

在一个二维网格地图上，你（用P表示）位于地图的某个位置，而幽灵（用G表示）位于另一个位置。地图中还可能存在墙壁（用#表示），墙壁是不可穿越的。你的目标是找到一条从当前位置到地图边缘（边缘定义为网格的第一行、最后一行、第一列或最后一列）的最短路径，以便逃离幽灵的追捕。如果无法逃离，则返回-1。

地图的大小是NxM，其中N是行数，M是列数。网格中的每个位置可以是空地（.）、墙壁（#）、你的位置（P）、幽灵的位置（G）或地图的边界。

示例输入

5 5
.G...
...#.
P...#
...#.
....#

示例输出

3

解释

在这个例子中，你从位置(2, 1)（即P的位置）出发，可以通过以下路径之一逃离到地图的边缘：(2, 1) -> (2, 2) -> (1, 2) -> (0, 2)，这条路径的长度是3。

示例代码

PHP 示例

function bfsEscape($grid) {
    $rows = count($grid);
    $cols = strlen($grid[0]);
    $startRow = $startCol = -1;
    $ghostRow = $ghostCol = -1;

    // 找到起点和幽灵的位置
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] === 'P') {
                $startRow = $i;
                $startCol = $j;
            } elseif ($grid[$i][$j] === 'G') {
                $ghostRow = $i;
                $ghostCol = $j;
            }
        }
    }

    // BFS 搜索
    $queue = new SplQueue();
    $queue->enqueue([$startRow, $startCol, 0]);
    $visited = array_fill(0, $rows, str_repeat(' ', $cols));
    $visited[$startRow][$startCol] = true;

    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    while (!$queue->isEmpty()) {
        [$row, $col, $steps] = $queue->dequeue();

        if (($row === 0 || $row === $rows - 1 || $col === 0 || $col === $cols - 1) && !($row === $ghostRow && $col === $ghostCol)) {
            return $steps;
        }

        foreach ($directions as $dir) {
            $newRow = $row + $dir[0];
            $newCol = $col + $dir[1];
            if ($newRow >= 0 && $newRow < $rows && $newCol >= 0 && $newCol < $cols && $grid[$newRow][$newCol] !== '#' && !$visited[$newRow][$newCol]) {
                $visited[$newRow][$newCol] = true;
                $queue->enqueue([$newRow, $newCol, $steps + 1]);
            }
        }
    }

    return -1; // 无法逃离
}

// 示例用法
$grid = [
    ".G...",
    "...#.",
    "P...#",
    "...#.",
    "....#"
];
echo bfsEscape($grid);

注意：PHP 示例中，我假设输入网格是一个二维数组，并且已经处理成了这种格式。实际使用时，你可能需要先将输入的字符串网格转换成二维数组。

Python 和 JavaScript 示例

由于篇幅限制，这里不再展开 Python 和 JavaScript 的完整示例代码，但它们的实现逻辑与 PHP 类似，都是使用 BFS（广度优先搜索）算法来寻找最短路径。在 Python 中，你可以使用列表的列表来表示二维网格，而在 JavaScript 中，你可以使用数组的数组或者二维数组对象。

希望这些示例能帮助你理解如何解决这个问题，并鼓励你进一步探索和学习算法相关的知识。码小课网站中有更多相关内容分享给大家学习，欢迎访问！

推荐面试题