当前位置: 面试刷题>> 洪水填充 (经典算法题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 代码示例

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

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

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);

码小课:在码小课网站上,你可以找到更多关于算法和数据结构的深入解析和实战练习,帮助你更好地掌握编程技能。

推荐面试题