当前位置： 面试刷题>> 洪水填充 (经典算法题500道)
### 题目描述补充
**洪水填充（Flood Fill）**
在一个二维网格中，每个单元格可以是空的（用 0 表示）或包含水的（用 1 表示）。给定一个网格的初始状态以及一个坐标 `(x, y)`，该坐标表示一个包含水的单元格。现在，你需要实现一个函数，该函数会将所有与给定坐标 `(x, y)` 相连的（上下左右四个方向）水单元格都填充为新的颜色值（假设为 2），并且只填充那些可以从给定单元格访问到的水单元格。
**注意**：
- 网格的边界是封闭的，即水不会流出网格的边界。
- 一个单元格只能被填充一次，即使它与多个已填充的单元格相连。
- 输入的网格至少包含一个水单元格。
### 示例
**输入**：
```
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 1]
]
x = 1, y = 1
```
**输出**：
```
[
[1, 1, 1],
[1, 2, 1],
[1, 2, 1]
]
```
### PHP 代码示例
```php
function floodFill(&$grid, $x, $y, $newColor) {
$rows = count($grid);
$cols = count($grid[0]);
$originalColor = $grid[$x][$y];
if ($originalColor == $newColor || $originalColor == 0) {
return;
}
function dfs(&$grid, $x, $y, $rows, $cols, $originalColor, $newColor) {
if ($x < 0 || $x >= $rows || $y < 0 || $y >= $cols || $grid[$x][$y] != $originalColor) {
return;
}
$grid[$x][$y] = $newColor;
dfs($grid, $x + 1, $y, $rows, $cols, $originalColor, $newColor);
dfs($grid, $x - 1, $y, $rows, $cols, $originalColor, $newColor);
dfs($grid, $x, $y + 1, $rows, $cols, $originalColor, $newColor);
dfs($grid, $x, $y - 1, $rows, $cols, $originalColor, $newColor);
}
dfs($grid, $x, $y, $rows, $cols, $originalColor, $newColor);
}
// 示例用法
$grid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 1]
];
floodFill($grid, 1, 1, 2);
print_r($grid);
```
### Python 代码示例
```python
def floodFill(grid, x, y, newColor):
if not grid or x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 1:
return
originalColor = grid[x][y]
def dfs(x, y):
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != originalColor:
return
grid[x][y] = newColor
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
dfs(x, y)
# 示例用法
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 1]
]
floodFill(grid, 1, 1, 2)
print(grid)
```
### JavaScript 代码示例
```javascript
function floodFill(grid, x, y, newColor) {
const rows = grid.length;
const cols = grid[0].length;
const originalColor = grid[x][y];
if (originalColor !== 1 || originalColor === newColor) {
return;
}
function dfs(x, y) {
if (
x < 0 || x >= rows || y < 0 || y >= cols ||
grid[x][y] !== originalColor
) {
return;
}
grid[x][y] = newColor;
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
dfs(x, y);
}
// 示例用法
const grid = [
[1, 1, 1],
[1, 0, 1],
[1, 0, 1]
];
floodFill(grid, 1, 1, 2);
console.log(grid);
```
**码小课**：在码小课网站上，你可以找到更多关于算法和数据结构的深入解析和实战练习，帮助你更好地掌握编程技能。