Flood fill

Given a start node, target color, and replacement color, write an algorithm that looks for all nodes in the grid that are connected to the start node by a path of the target color, and changes them to the replacement color

Picture by André Karwath aka Aka - Own work, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=481651

Example:

Given the matrix below. Start node is (1, 2). Target color (‘ ‘). Replacement color ‘g’:

{'r', 'r', ' ', 'r'};
{'r', ' ', ' ', 'r'};
{'r', 'r', ' ', 'r'};
{'r', ' ', 'r', 'r'};

The output should be:

{'r', 'r', 'g', 'r'};
{'r', 'g', 'g', 'r'};
{'r', 'r', 'g', 'r'};
{'r', ' ', 'r', 'r'};

Approach (Recursive)

The brute force approach is pretty straight forward If you know how to iterate recursively though a grid (like we did in the boggle question and Find the fastest route).

We can implement a simple recursion that travels through all the adjacent nodes (up, down, left and right),  for each node: if the node color is the target color, change it, otherwise break.

Since we move in both directions (down and up, right and left), we need to make sure that we don’t visit the same node more than once to avoid a circular flow.

However, the problem with a recursive approach is that for a large grid we will likely to run out of stack.

Approach (Breath First)

A better approach for this problem would be using breath first search, which is implemented iteratively using a queue (same as breath first tree traversal).

Tests

public class PaintFillerTest {
    private static final boolean USE_BREATH_FIRST = false;

    @Test
    public void fill_small() throws Exception {

        Matrix matrix = new Matrix(getSmallMatrix());

        PaintFiller paintFiller = createPaintFiller(USE_BREATH_FIRST);

        paintFiller.fill(matrix, 1, 2, ' ', 'g');

        Matrix expectedMatrix = new Matrix(getExpectedSmallMatrix());
        compareMatrix(matrix, expectedMatrix);
    }

    @Test
    public void fill_big() throws Exception {

        Matrix matrix = new Matrix(getBigMatrix());

        PaintFiller paintFiller = createPaintFiller(USE_BREATH_FIRST);

        paintFiller.fill(matrix, 4, 1, ' ', 'g');

        Matrix expectedMatrix = new Matrix(getExpectedBigMatrix());
        compareMatrix(matrix, expectedMatrix);
    }

    private PaintFiller createPaintFiller(boolean useBreathFirst) {
        if (useBreathFirst) {
            return new PaintFillerBreathFirst();
        }
        return new PaintFillerRecursive();
    }

    private void compareMatrix(Matrix matrix, Matrix expectedMatrix) {
        for (int row = 0; row < matrix.getRows(); row++) {
            for (int column = 0; column < matrix.getColumns(); column++) {
                final Character expected = expectedMatrix.get(row, column);
                final Character actual = matrix.get(row, column);
                final String message = String.format("Mismatch at row: %d, col: %d", row, column);
                assertEquals(message, expected, actual);
            }
        }
    }

    private char[][] getSmallMatrix() {
        char[][] matrix = new char[4][];
        matrix[0] = new char[]{'r', 'r', ' ', 'r'};
        matrix[1] = new char[]{'r', ' ', ' ', 'r'};
        matrix[2] = new char[]{'r', 'r', ' ', 'r'};
        matrix[3] = new char[]{'r', ' ', 'r', 'r'};
        return matrix;
    }

    private char[][] getExpectedSmallMatrix() {
        char[][] matrix = new char[4][];
        matrix[0] = new char[]{'r', 'r', 'g', 'r'};
        matrix[1] = new char[]{'r', 'g', 'g', 'r'};
        matrix[2] = new char[]{'r', 'r', 'g', 'r'};
        matrix[3] = new char[]{'r', ' ', 'r', 'r'};
        return matrix;
    }

    private char[][] getBigMatrix() {
        char[][] matrix = new char[6][];
        matrix[0] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[1] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[2] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[3] = new char[]{'r', 'r', 'r', 'r', ' ', ' '};
        matrix[4] = new char[]{'r', ' ', ' ', 'r', ' ', ' '};
        matrix[5] = new char[]{'r', ' ', 'r', 'r', ' ', ' '};
        return matrix;
    }

    private char[][] getExpectedBigMatrix() {
        char[][] matrix = new char[6][];
        matrix[0] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[1] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[2] = new char[]{'r', ' ', ' ', ' ', ' ', ' '};
        matrix[3] = new char[]{'r', 'r', 'r', 'r', ' ', ' '};
        matrix[4] = new char[]{'r', 'g', 'g', 'r', ' ', ' '};
        matrix[5] = new char[]{'r', 'g', 'r', 'r', ' ', ' '};
        return matrix;
    }
}

Solution (Recursive)

public class PaintFillerRecursive implements PaintFiller {

    @Override
    public void fill(Matrix matrix, int rowIndex, int columnIndex, char target, char replacement) {
        Boolean[][] visited = PaintFillerTool.createdVisitedMatrix(matrix);

        fillRecursive(matrix, rowIndex, columnIndex, visited, target, replacement);
    }

    private static void fillRecursive(
            Matrix matrix,
            int rowIndex,
            int columnIndex,
            Boolean[][] visited,
            char target,
            char replacement) {

        if (!matrix.isInRange(rowIndex, columnIndex)) {
            return;
        }

        if (visited[rowIndex][columnIndex]) {
            return;
        }
        visited[rowIndex][columnIndex] = true;

        final Character nextColor = matrix.get(rowIndex, columnIndex);
        if (nextColor != target) {
            return;
        }

        // Apply color
        matrix.set(rowIndex, columnIndex, replacement);

        // Look downward
        fillRecursive(matrix, rowIndex + 1, columnIndex, visited, target, replacement);

        // Look up
        fillRecursive(matrix, rowIndex - 1, columnIndex, visited, target, replacement);

        // Look to the right
        fillRecursive(matrix, rowIndex, columnIndex + 1, visited, target, replacement);

        // Look to the left
        fillRecursive(matrix, rowIndex, columnIndex - 1, visited, target, replacement);
    }
}

Solution (Breath first)

public class PaintFillerBreathFirst implements PaintFiller {
    @Override
    public void fill(Matrix matrix, int rowIndex, int columnIndex, char target, char replacement) {
        LinkedList<MatrixPoint> queue = new LinkedList<>();

        Boolean[][] visited = PaintFillerTool.createdVisitedMatrix(matrix);

        queue.add(new MatrixPoint(rowIndex, columnIndex));

        while (!queue.isEmpty()) {
            MatrixPoint nextPoint = queue.poll();
            rowIndex = nextPoint.row;
            columnIndex = nextPoint.column;

            // Check range
            if (!matrix.isInRange(rowIndex, columnIndex)) {
                continue;
            }

            // Don't visit the same node twice
            if (visited[rowIndex][columnIndex]) {
                continue;
            }

            // Check if cell needs replacement
            final Character nextColor = matrix.get(rowIndex, columnIndex);
            if (nextColor != target) {
                continue;
            }
            // Apply color
            matrix.set(rowIndex, columnIndex, replacement);

            // Add next steps to the adjacent nodes (up, down, right, left)
            queue.add(new MatrixPoint(rowIndex + 1, columnIndex));
            queue.add(new MatrixPoint(rowIndex - 1, columnIndex));
            queue.add(new MatrixPoint(rowIndex, columnIndex + 1));
            queue.add(new MatrixPoint(rowIndex, columnIndex - 1));

        }
    }
}