算法：披萨切割

Question

我正在尝试解决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.

披萨最多由 50 行和 50 列组成，并且 k <= 10。

目前，我有一个非常基本的暴力解决方案，我计划稍后对其进行优化。

这是我的代码：

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;
    }
}

这没有通过以下测试用例：[".A..A","A.A..","A.AA.","AAAA.","A.AA."] 5

预期结果是153，然而，我的代码returns141.

我不明白为什么，希望得到任何帮助。

谢谢！

Answer 1

你只是在切苹果的相邻位置，但在苹果之间切也可以。

例如，考虑底行“A.AA.”，因此您在第 1,3 和 4 列之后进行剪切（尽管 4 被证明是无效的）。但是，你错过了你也可以在第 2 列之后剪切！

算法：披萨切割

Algorithms : Pizza Cutting

algorithm

dynamic-programming

depth-first-search