题目描述补充

题目：矩阵找数

给定一个二维矩阵（二维数组）matrix和一个目标值target，要求编写一个算法来查找该矩阵中是否存在路径，使得从矩阵的左上角出发，只能向右或向下移动，路径上的数字之和恰好等于target。如果找到这样的路径，则返回true；否则返回false。

示例

假设矩阵如下：

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

目标值target为12，则存在一条路径1 -> 5 -> 6，其和为12，因此应返回true。

PHP 示例代码

function hasPathSum($matrix, $target) {
    if (empty($matrix) || empty($matrix[0])) {
        return false;
    }
    
    $rows = count($matrix);
    $cols = count($matrix[0]);
    
    return dfs($matrix, 0, 0, $target, $rows, $cols);
}

function dfs($matrix, $row, $col, $target, $rows, $cols) {
    if ($row >= $rows || $col >= $cols) {
        return false;
    }
    
    if ($row == $rows - 1 && $col == $cols - 1) {
        return $matrix[$row][$col] == $target;
    }
    
    $currentSum = $matrix[$row][$col];
    
    // 尝试向右走
    $right = dfs($matrix, $row, $col + 1, $target - $currentSum, $rows, $cols);
    // 如果向右走找到了解，则直接返回true
    if ($right) {
        return true;
    }
    
    // 尝试向下走
    $down = dfs($matrix, $row + 1, $col, $target - $currentSum, $rows, $cols);
    return $down;
}

// 示例用法
$matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
$target = 12;
echo hasPathSum($matrix, $target) ? "true" : "false";  // 输出: true

Python 示例代码

def hasPathSum(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    def dfs(row, col, current_sum):
        if row == len(matrix) or col == len(matrix[0]):
            return False
        if row == len(matrix) - 1 and col == len(matrix[0]) - 1:
            return current_sum + matrix[row][col] == target
        
        current_sum += matrix[row][col]
        return dfs(row + 1, col, current_sum) or dfs(row, col + 1, current_sum)
    
    return dfs(0, 0, 0)

# 示例用法
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
target = 12
print(hasPathSum(matrix, target))  # 输出: True

JavaScript 示例代码

function hasPathSum(matrix, target) {
    if (!matrix || !matrix.length || !matrix[0].length) {
        return false;
    }
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    
    function dfs(row, col, currentSum) {
        if (row >= rows || col >= cols) {
            return false;
        }
        
        if (row === rows - 1 && col === cols - 1) {
            return currentSum + matrix[row][col] === target;
        }
        
        currentSum += matrix[row][col];
        return dfs(row + 1, col, currentSum) || dfs(row, col + 1, currentSum);
    }
    
    return dfs(0, 0, 0);
}

// 示例用法
const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const target = 12;
console.log(hasPathSum(matrix, target)); // 输出: true

码小课网站分享

码小课网站中有更多关于算法和数据结构的相关内容，包括但不限于矩阵操作、动态规划、深度优先搜索等，欢迎大家访问学习，共同进步。