当前位置: 面试刷题>> 能否到达终点 (经典算法题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代码示例

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代码示例

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代码示例

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)算法来解决问题,并在搜索过程中通过修改网格中的值来避免重复访问相同的格子。在递归回溯时,需要将修改过的网格值恢复,以便后续可能的搜索路径可以使用。

推荐面试题