当前位置： 面试刷题>> 矩阵注水 (经典算法题500道)
### 题目描述补充
**题目：矩阵注水（Matrix Water Pouring）**
给定一个二维矩阵，矩阵的每个单元格代表一个水池的初始水位（初始时，大多数单元格的水位为0，但可能有一些单元格的水位不为0）。现在，你有一个无限的水源，你可以从矩阵的任意边界上的单元格开始注水，直到水充满整个矩阵或达到某个特定的水位限制（假设所有单元格的水位上限都是相同的，且足够大以容纳所有注入的水）。水在矩阵中按照“四向扩散”的方式流动，即水可以从一个单元格流向其上下左右四个相邻的单元格（如果存在且水位更低）。
任务：编写一个函数，该函数接受一个二维整数数组（表示初始水位矩阵）和一个整数`target`作为参数，返回是否可以从矩阵的边界开始注水，直到至少有一个单元格的水位达到或超过`target`。
### 示例
**输入**：
```plaintext
matrix = [
[1, 1, 1],
[0, 1, 0],
[1, 1, 0]
]
target = 2
```
**输出**：
```plaintext
true
```
**解释**：
可以从矩阵的顶部或底部开始注水，水会扩散到整个矩阵，使得所有单元格的水位都至少达到2。
### PHP 代码示例
```php
function canFillToTarget($matrix, $target) {
$rows = count($matrix);
if ($rows == 0) return false;
$cols = count($matrix[0]);
// 定义四个方向的偏移量
$directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
// 创建一个同样大小的矩阵来记录每个单元格的水位是否达到或超过target
$reached = array_fill(0, $rows, array_fill(0, $cols, false));
// 定义边界的起始点
$queue = new SplQueue();
for ($i = 0; $i < $rows; $i++) {
// 第一行和最后一行
$queue->enqueue([$i, 0]);
$queue->enqueue([$i, $cols - 1]);
$reached[$i][0] = $reached[$i][$cols - 1] = true;
// 第一列和最后一列
$queue->enqueue([0, $i]);
$queue->enqueue([$rows - 1, $i]);
$reached[0][$i] = $reached[$rows - 1][$i] = true;
}
// 广度优先搜索
while (!$queue->isEmpty()) {
[$row, $col] = $queue->dequeue();
$currentLevel = $matrix[$row][$col];
if ($currentLevel >= $target) {
return true;
}
foreach ($directions as $dir) {
$newRow = $row + $dir[0];
$newCol = $col + $dir[1];
if ($newRow >= 0 && $newRow < $rows && $newCol >= 0 && $newCol < $cols && !$reached[$newRow][$newCol]) {
$reached[$newRow][$newCol] = true;
$queue->enqueue([$newRow, $newCol]);
// 假设水会平均分配到相邻的单元格，这里简化为只增加1
$matrix[$newRow][$newCol] = max($matrix[$newRow][$newCol], $currentLevel + 1);
}
}
}
return false;
}
```
**注意**： 以上PHP代码是一个简化的实现，它假设水会平均分配到相邻的单元格，但这里为了简化处理，我们仅使水位增加1。在实际问题中，你可能需要更复杂的逻辑来处理水位增长。
**码小课**：在算法和数据结构的学习中，矩阵操作和广度优先搜索（BFS）是常见的主题。码小课网站提供了丰富的教程和练习题，可以帮助你深入理解这些概念，并提升解决实际问题的能力。