FloodFill implementation in recursive manner

Question

Flood fill means that it takes initial rectangular area containing land and water cells and imitates flooding it: each flood step water cell converts neighbour land cells (up, left, right and down) to water.

It takes some steps to completely flood an area and after that algorithm stops. We must implement FloodFill in recursive manner and make flood method call itself until all the area becomes water.

But something goes wrong. What is my problem?

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

The algorithm cannot just scan and change the array in one pass!

---

Negative example, how it does not work!

Just one row (one-dimensional) and using W and L instead of ░ and █. Lets start with WLLL and work left to right:
0 is Water → nothing done: WLLL
1 is Land and has neighbor Water → changed to Water: WWLL
2 is Land and (now) has neighbor Water → changed to Water:WWWL
3 same as above: WWWW
at the end of one iteration the whole row is Water.

This will not happen if working right to left:
3 is Land but no Water neighbor → nothing changed: WLLL
2 is Land but no Water neighbor → nothing changed: WLLL
1 is Land with Water neighbor → changed to Water: WWLL
0 is Water → nothing changed: WWLL
now only only Land was changed to Water.

Similar will also happen with subsequent rows, two-dimensional map.

---

Some suggestions:

• use a temporary array to hold the old, new, or changed state; or
• use a third value to mark cells that will change (e.g. SWAMP); or
• ... ?

---

Pseudocode first option, using a boolean array to hold the values to be changed:

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

_{obviously using correct dimensions, indices, methods, ...}
^{This is a single iteration, it must be repeated until the map is not further changed.}

---

Pseudocode second option, using a third value in map, to denote the values to be changed:

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

Note: nearWater should not consider SWAMP as being WATER!
_{obviously using correct dimensions, indices, methods, ...}
^{This is a single iteration, it must be repeated until the map is not further changed.}

---

This is not the algorithm called Flood Fill!
The Flood Fill algorithm usually starts at a single position and floods its neighbors recursively - it usually does not scan the whole map.