当前位置： 面试刷题>> 迷宫 (经典算法题500道)
**题目描述补充**：
给定一个二维数组（迷宫），其中`0`表示可走的路径，`1`表示障碍物（墙壁）。迷宫中只有一个入口（左上角）和一个出口（右下角）。要求编写一个算法，判断从入口到出口是否存在一条路径，如果存在则返回`true`，否则返回`false`。
**示例输入**：
```
[
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
```
**示例输出**：
```
true
```
**算法思路**：
可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题。这里，我们将使用深度优先搜索作为示例来解答。
**PHP 示例代码**：
```php
function hasPath($maze) {
if (empty($maze) || empty($maze[0])) {
return false;
}
$rows = count($maze);
$cols = count($maze[0]);
// 深度优先搜索函数
function dfs($maze, $i, $j, &$visited) {
$rows = count($maze);
$cols = count($maze[0]);
// 边界条件：到达右下角出口
if ($i == $rows - 1 && $j == $cols - 1) {
return true;
}
// 标记当前位置已访问
$visited[$i][$j] = true;
// 四个方向的偏移量
$directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
foreach ($directions as $dir) {
$newX = $i + $dir[0];
$newY = $j + $dir[1];
// 检查新位置是否合法且可走且未访问过
if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && !$visited[$newX][$newY] && $maze[$newX][$newY] == 0) {
if (dfs($maze, $newX, $newY, $visited)) {
return true;
}
}
}
// 回溯，标记当前位置为未访问（可选，因为最终会遍历完所有路径）
$visited[$i][$j] = false;
return false;
}
$visited = array_fill(0, $rows, array_fill(0, $cols, false));
return dfs($maze, 0, 0, $visited);
}
// 示例用法
$maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
];
echo hasPath($maze) ? "true" : "false";
```
**Python 示例代码**：
```python
def hasPath(maze):
if not maze or not maze[0]:
return False
rows, cols = len(maze), len(maze[0])
def dfs(i, j, visited):
if i == rows - 1 and j == cols - 1:
return True
visited[i][j] = True
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dx, dy in directions:
newX, newY = i + dx, j + dy
if 0 <= newX < rows and 0 <= newY < cols and not visited[newX][newY] and maze[newX][newY] == 0:
if dfs(newX, newY, visited):
return True
return False
visited = [[False] * cols for _ in range(rows)]
return dfs(0, 0, visited)
# 示例用法
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
print(hasPath(maze)) # 输出: True
```
**JavaScript 示例代码**：
```javascript
function hasPath(maze) {
if (!maze.length || !maze[0].length) {
return false;
}
const rows = maze.length;
const cols = maze[0].length;
function dfs(i, j, visited) {
if (i === rows - 1 && j === cols - 1) {
return true;
}
visited[i][j] = true;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for (const [dx, dy] of directions) {
const newX = i + dx;
const newY = j + dy;
if (
newX >= 0 && newX < rows &&
newY >= 0 && newY < cols &&
!visited[newX][newY] &&
maze[newX][newY] === 0
) {
if (dfs(newX, newY, visited)) {
return true;
}
}
}
return false;
}
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
return dfs(0, 0, visited);
}
// 示例用法
const maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
];
console.log(hasPath(maze)); // 输出: true
```
**码小课**网站中有更多相关内容分享给大家学习，包括但不限于算法题解、编程技巧、数据结构等，欢迎大家访问学习。