当前位置： 面试刷题>> 矩阵找数 (经典算法题500道)
### 题目描述补充
题目：**矩阵找数**
给定一个二维矩阵（二维数组）`matrix`和一个目标值`target`，要求编写一个算法来查找该矩阵中是否存在路径，使得从矩阵的左上角出发，只能向右或向下移动，路径上的数字之和恰好等于`target`。如果找到这样的路径，则返回`true`；否则返回`false`。
### 示例
假设矩阵如下：
```
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
```
目标值`target`为`12`，则存在一条路径`1 -> 5 -> 6`，其和为`12`，因此应返回`true`。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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
```
### 码小课网站分享
码小课网站中有更多关于算法和数据结构的相关内容，包括但不限于矩阵操作、动态规划、深度优先搜索等，欢迎大家访问学习，共同进步。