FloodFill 递归实现

Question

洪水填充意味着它采用包含陆地和水单元格的初始矩形区域并模拟洪水： 每个洪水步骤水单元将相邻的陆地单元（上、左、右和下）转换为水。

需要一些步骤才能完全淹没一个区域，然后算法停止。 我们必须以递归方式实现 FloodFill 并使 flood 方法自行调用，直到所有区域都变成水。

但是出了点问题。我的问题是什么？

class RecursiveFloodFill implements FloodFill {
    private char[][] grid;

  @Override
public void flood(final String map, final FloodLogger logger) {
    logger.log(map);
    String newMap = floodStep(map);
    if (!newMap.equals(map)) {
        flood(newMap, logger);
    }
}

private String floodStep(final String map) {
    char[][] area = stringToArea(map);
    char[][] newArea = new char[area.length][area[0].length];
    for (int row = 0; row < area.length; row++) {
        System.arraycopy(area[row], 0, newArea[row], 0, area[row].length);
    }

    for (int row = 0; row < area.length; row++) {
        for (int col = 0; col < area[row].length; col++) {
            if (area[row][col] == WATER) {
                    newArea[row - 1][col] = WATER;
                    newArea[row + 1][col] = WATER;
                    newArea[row][col - 1] = WATER;
                    newArea[row][col + 1] = WATER;
                }
            }
        }
    }
    return areaToString(newArea);
}

Answer 1

算法不能一次性扫描和改变数组！

---

负示例，它是如何不起作用！

只有一行（一维）并使用

W

和

L

而不是

░

和

█

。让我们从

WLLL

开始，从左到右工作：

0

是水 → 什么都没做：

WLLL

1

是 Land 并且有邻居 Water → 更改为 Water：

WWLL

2

是土地并且（现在）有邻居水 → 改为水：

WWWL

3

同上：

WWWW

在一次迭代结束时，整行都是水。

如果从右向左工作就不会发生这种情况：

3

是陆地但没有水邻居 → 没有改变：

WLLL

2

是陆地但没有水邻居 → 没有改变：

WLLL

1

是 Land with Water 邻居 → 更改为 Water：

WWLL

0

是水 → 没有改变：

WWLL

现在只有陆地变成了水。

类似的情况也会发生在后续的行中，二维地图。

---

一些建议：

• 使用临时数组来保存旧的、新的或更改的状态；或
• 使用第三个值来标记将要改变的单元格（例如 SWAMP）；或
• ... ?

---

伪代码第一个选项，使用布尔数组来保存要更改的值：

change = new boolean[][]

// first pass
for i : rows
  for j : columns
    change[i][j] = map[i][j] is LAND and nearWater

// second pass
for i : rows
  for j : columns
    if change[i][j]
      map[i][j] = WATER

_{显然使用正确的维度、指标、方法，...}
^{这是单次迭代，必须重复直到地图不再发生变化。}

---

伪代码第二个选项，使用地图中的第三个值来表示要更改的值：

SWAMP = '#'

// first pass
for i : rows
  for j : columns
    if map[i][j] is LAND and nearWater
      map[i][j] = SWAMP

// second pass
for i : rows
  for j : columns
    if map[i][j] is SWAMP
      map[i][j] = WATER

注意：

nearWater

不应将沼泽视为水！
_{显然使用正确的维度、指标、方法，...}
^{这是单次迭代，必须重复直到地图不再发生变化。}

---

这不是所谓的算法Flood Fill！
Flood Fill 算法通常从一个位置开始，然后递归地 floods 它的邻居——它通常不会扫描整个地图。