当前位置： 面试刷题>> 能否到达终点 (经典算法题500道)
**题目描述补充**：
给定一个二维网格（二维数组），其中每个格子可以是0（表示可以通行）或1（表示障碍物）。网格的左上角是起点 `(0, 0)`，右下角是终点 `(m-1, n-1)`（其中 `m` 是网格的行数，`n` 是网格的列数）。你可以向上、下、左、右四个方向移动。请问是否存在一条从起点到终点的路径，使得路径上所有的格子都是0？
**示例输入**：
```
[[0,0,0],[0,1,0],[0,0,0]]
```
**示例输出**：
```
true
```
**解释**：
给定的网格是一个3x3的二维数组，其中除了 `(1, 1)` 位置是1（障碍物）外，其余都是0（可以通行）。从 `(0, 0)` 到 `(2, 2)` 存在一条路径，例如 `(0,0) -> (0,1) -> (0,2) -> (2,2)`。
**PHP代码示例**：
```php
function canReachDestination($grid) {
$m = count($grid);
$n = count($grid[0]);
// 定义一个辅助函数来进行深度优先搜索
function dfs(&$grid, $row, $col, $m, $n) {
// 检查边界条件和障碍物
if ($row < 0 || $row >= $m || $col < 0 || $col >= $n || $grid[$row][$col] == 1) {
return false;
}
// 如果到达终点，则返回true
if ($row == $m - 1 && $col == $n - 1) {
return true;
}
// 标记当前位置为已访问（防止重复访问）
$grid[$row][$col] = 1;
// 尝试四个方向
$directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
foreach ($directions as $dir) {
$newRow = $row + $dir[0];
$newCol = $col + $dir[1];
if (dfs($grid, $newRow, $newCol, $m, $n)) {
return true;
}
}
// 恢复当前位置为可访问（回溯）
$grid[$row][$col] = 0;
return false;
}
return dfs($grid, 0, 0, $m, $n);
}
// 示例用法
$grid = [[0,0,0],[0,1,0],[0,0,0]];
echo canReachDestination($grid) ? 'true' : 'false';
```
**Python代码示例**：
```python
def canReachDestination(grid):
m, n = len(grid), len(grid[0])
def dfs(row, col):
# 检查边界条件和障碍物
if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] == 1:
return False
# 如果到达终点，则返回True
if row == m - 1 and col == n - 1:
return True
# 标记当前位置为已访问
grid[row][col] = 1
# 尝试四个方向
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
if dfs(row + dr, col + dc):
return True
# 恢复当前位置为可访问（回溯）
grid[row][col] = 0
return False
return dfs(0, 0)
# 示例用法
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(canReachDestination(grid)) # 输出: True
```
**JavaScript代码示例**：
```javascript
function canReachDestination(grid) {
const m = grid.length;
const n = grid[0].length;
function dfs(row, col) {
// 检查边界条件和障碍物
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === 1) {
return false;
}
// 如果到达终点，则返回true
if (row === m - 1 && col === n - 1) {
return true;
}
// 标记当前位置为已访问
grid[row][col] = 1;
// 尝试四个方向
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of directions) {
if (dfs(row + dr, col + dc)) {
return true;
}
}
// 恢复当前位置为可访问（回溯）
grid[row][col] = 0;
return false;
}
return dfs(0, 0);
}
// 示例用法
const grid = [[0,0,0],[0,1,0],[0,0,0]];
console.log(canReachDestination(grid)); // 输出: true
```
**注意**： 以上代码示例都使用了深度优先搜索（DFS）算法来解决问题，并在搜索过程中通过修改网格中的值来避免重复访问相同的格子。在递归回溯时，需要将修改过的网格值恢复，以便后续可能的搜索路径可以使用。