泛洪填充是指它采用包含土地和水单元的初始矩形区域并模拟泛洪：每个洪水步骤水单元将相邻的陆地单元（上、左、右和下）转换为水。
它需要一些步骤来完全淹没一个区域，然后算法停止。我们必须以递归方式实现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);
}
1条答案
按热度按时间2hh7jdfx1#
算法不能一次扫描和修改数组！
只有一行（一维），使用
W和L，而不是░和█。让我们从WLLL开始，从左到右工作：0是水→什么也没做：WLLL1是陆地，相邻水域→变更为水域：WWLL2是土地，（现在）有邻居水→改为水：WWWL3同上：WWWW在一次迭代结束时，整行都是水。
如果从右到左工作，则不会发生这种情况：
3是陆地但没有水的邻居→没有变化：WLLL2是陆地但没有水的邻居→没有变化：WLLL1是有水的陆地邻居→改为水：WWLL0是水→没有变化：WWLL现在只有陆地变成了水。
类似的情况也会发生在后续的行、二维图中。
一些建议：
伪代码第一个选项，使用布尔数组保存要更改的值：
显然使用正确的尺寸、指数、方法……
这是一个单一的迭代，它必须重复，直到Map没有进一步改变。
伪代码第二个选项，使用map中的第三个值来表示要更改的值：
注意：
nearWater不应该认为SWAMP是水！显然使用正确的尺寸、指数、方法……
这是一个单一的迭代，它必须重复，直到Map没有进一步改变。
这不是名为Flood Fill的算法！
Flood Fill 算法通常从单个位置开始，递归地 * flood * 其邻居-它通常不会扫描整个Map。