Algorithms : Pizza Cutting

Question

I'm trying to solve https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

The pizza consists of at most 50 rows and columns, and k <= 10.

For now, I have a very basic, brute force solution, which I plan to optimize later on.

Here's my code :

class Solution {
    long combos;
    public int ways(String[] pizza, int k) {
        Set<String> remaining = new HashSet<String>();
        this.combos = 0;
        for(int i = 0; i < pizza.length; i++) {
            for(int j = 0; j < pizza[i].length(); j++) {
                char ch = pizza[i].charAt(j);
                if(ch == 'A') remaining.add(i + "," + j);
            }
        }

        getCombos(remaining, k - 1);
        return (int)(combos % (1000000007));
    }

    public void getCombos(Set<String> remaining, int k) {
        if(remaining.isEmpty()) return;
        if(k == 0) {
            combos++;
            return;
        }

        Set<Integer> seenCol = new HashSet<Integer>();
        Set<Integer> seenRow = new HashSet<Integer>();
        for(String apple : remaining) {
            String[] posStr = apple.split(",");

            int i = Integer.parseInt(posStr[0]);
            int j = Integer.parseInt(posStr[1]);

            // cut below this
            Set<String> below = getBelow(i, j, remaining);
            if(!seenRow.contains(i))  {seenRow.add(i);getCombos(below, k - 1);}

            // cut right
            Set<String> right = getRight(i, j, remaining);
            if(!seenCol.contains(j)) {seenCol.add(j);getCombos(right, k - 1);}
        }
    }

    public Set<String> getBelow(int i, int j, Set<String> remaining) {
        Set<String> result = new HashSet<String>();
        for(String apple : remaining) {
            String[] coords = apple.split(",");
            if(Integer.parseInt(coords[0]) > i) result.add(apple);
        }
        return result;
    }

    public Set<String> getRight(int i, int j, Set<String> remaining) {
        Set<String> result = new HashSet<String>();
        for(String apple : remaining) {
            String[] coords = apple.split(",");
            if(Integer.parseInt(coords[1]) > j) result.add(apple);
        }
        return result;
    }
}

This doesn't pass the following test case : [".A..A","A.A..","A.AA.","AAAA.","A.AA."] 5

The expected result is 153, however, my code returns 141.

I can't figure out why and would appreciate any help.

Thank you!

Answer 1

You are only cutting adjacent to an apple, but cutting between apples can also be valid.

For example, consider that bottom row “A.AA.”, so you cut after columns 1,3 and 4 (although 4 turns out to be invalid). However, you are missing that you can also cut after column 2 !