Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Strokes to paint

Sharing is caring!

Problem Statement
Alex wants to paint a picture but hates taking the brush off the canvas. In one stroke, Alex can only paint the same colored cells which are joined via some edge.

Given the painting, determine the minimum number of strokes to completely paint the picture.

Take for example, the canvas with height given by h = 3 and width given by w = 5 is to be painted with picture picture=[“aabba”, “aabba”, “aaaca”], the diagram below shows the 4 strokes needed to paint the canvas.

        Strokes
 Canvas  1   2  3 4
 aabba   aa  bb   a
 aabba   aa  bb   a
 aaaca   aaa    c a

Function Description
Complete the function strokesRequired in the editor below. The function must return an integer, the minimum number of strokes required to paint the canvas.

strokesRequired has the following parameter(s):
picture[picture[0],…picture[h-1]]: an array of strings where each string represents one row of the picture to be painted

Constraints
1 ≤ h ≤ 105
1 ≤ w ≤ 105
1 ≤ h*w ≤ 105
len(picture[i]) = w (where 0 ≤ i < h)
picture[i][j] ∈ {‘a’, ‘b’, ‘c’} (where 0 ≤ i < h and 0 ≤ j < w)

Sample Input For Custom Testing

3
aaaba
ababa
aaaca

Sample Output

5

Explanation
The ‘a’s can be painted in 2 strokes, ‘b’s in 2 strokes and ‘c’ in 1 stroke, for a total of 5.

        Strokes
 Canvas  1   2 3 4 5
 aaaba  aaa    b   a
 ababa  a a  b b   a
 aaaca  aaa      c a

Solution

public class StrokesToPaint {
    static char VISITED = 'x';

    public static void print(char[][] painting) {
        int rows = painting.length;
        int cols = painting[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                System.out.print(painting[r][c]);
            }
            System.out.println();
        }
        System.out.println("------------------------------------");
    }

    public static boolean isValid(int i, int j, char[][] painting, char checkChar) {
        int rows = painting.length;
        int cols = painting[0].length;

        if (i < 0 || j < 0 || i >= rows || j >= cols || painting[i][j] != checkChar) {
            return false;
        } else {
            return true;
        }
    }


    public static void dfs(char[][] painting, int r, int c, char checkChar) {
        painting[r][c] = VISITED;

        // With Diagonals
        // int[] ith = {0, 1, 1, -1, 0, -1, -1, 1};
        // int[] jth = {1, 0, 1, 0, -1, -1, 1, -1};

        int[] ith = {0, 1, -1, 0};
        int[] jth = {1, 0, 0, -1};
        for (int k = 0; k < ith.length; k++) {
            if (isValid(r + ith[k], c + jth[k], painting, checkChar)) {
                dfs(painting, r + ith[k], c + jth[k], checkChar);
            }
        }
    }

    public static int strokesRequired(char[][] painting) {
        int rows = painting.length;
        int cols = painting[0].length;

        // Start a DFS from every non visited cell
        int numberOfComponents = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (painting[r][c] != VISITED) {
                    numberOfComponents++;
                    dfs(painting, r, c, painting[r][c]);
                }
            }
        }

        return numberOfComponents;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in11.txt"));
        //Scanner outputScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        char[][] painting = new char[n][];
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            painting[i] = s.toCharArray();
        }

        System.out.println(strokesRequired(painting));
    }
}