FillRegionsMapInterviewTask (related to The Four-Color Theorem)

FillRegionsMapInterviewTask.java

package com.example.demo;

import java.util.Arrays;

public class FillRegionsMapInterviewTask {
    // The Four-Color Theorem
    //
    // In mathematics, the four color theorem, or the four color map theorem,
    // states that no more than four colors are required to color the regions
    // of any map so that no two adjacent regions have the same color.
  
    public static void main(String[] args) {
        int[][] A = {
                {1, 2, 2, 2},
                {1, 3, 4, 2},
                {2, 2, 4, 4}
        };

        var foundRegions = findSolution(deepCopy(A));

        System.out.println("Found regions: " + foundRegions);
    }

    public static int FOUND_COLOR = 0;

    public static int findSolution(final int[][] A) {
        if (A == null) {
            return 0;
        }
        int regions = 0;
        printMap(A);

        for (int x = 0; x < A.length; x++) {
            for (int y = 0; y < A[x].length; y++) {
                var el = A[x][y];
                if (el != FOUND_COLOR) {
                    regions++;
                    fillRegion(A, x, y, el);
                    printMap(A);
                }
            }
        }

        return regions;
    }

    private static void fillRegion(int[][] A, int x, int y, int colorToReplace) {
        if ((x < 0 || x >= A.length) || (y < 0 || y >= A[x].length)) {
            return;
        }

        var curColor = A[x][y];
        if (curColor != colorToReplace) {
            return;
        }

        if (curColor == FOUND_COLOR) {
            return;
        }

        A[x][y] = FOUND_COLOR;

        fillRegion(A, x, y - 1, curColor);
        fillRegion(A, x, y + 1, curColor);
        fillRegion(A, x - 1, y, curColor);
        fillRegion(A, x + 1, y, curColor);
    }

    public static void printMap(int[][] A) {
        for (int[] ints : A) {
            for (int j = 0; j < ints.length; j++) {
                System.out.print(ints[j]);
                if (j == ints.length - 1) {
                    System.out.println();
                } else {
                    System.out.print(" ");
                }
            }
        }
        System.out.println();
    }

    public static int[][] deepCopy(int[][] array) {
        if (array == null) {
            return null;
        }

        return Arrays.stream(array)
                .map(int[]::clone)
                .toArray(s -> array.clone());
    }
}