当前位置： 面试刷题>> 逃离幽灵 (经典算法题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 示例
```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 中，你可以使用数组的数组或者二维数组对象。
希望这些示例能帮助你理解如何解决这个问题，并鼓励你进一步探索和学习算法相关的知识。码小课网站中有更多相关内容分享给大家学习，欢迎访问！