算法：切比萨饼

Question

我正在尝试解决https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/

给出一个矩形披萨，表示为x列的行矩阵包含以下字符：“ A”（苹果）和“。” （空单元格）并给出整数k。你要把披萨切成K片使用k-1削减

对于每个切割，请选择方向：垂直或水平，然后您在单元格边界处选择一个切开位置，然后将比萨切成两块。如果您垂直切比萨饼，请在披萨给一个人。如果水平切比萨饼，请给上面比萨饼的一部分给一个人。将最后一块披萨送给最后一个人。

返回切割比萨饼的方法，以使每一块包含至少一个苹果。由于答案可能很多，返回此模10 ^ 9 + 7。

[比萨饼最多包含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，但是我的代码返回141。

我不知道为什么，将不胜感激。

谢谢！

Answer 1

您仅在与苹果相邻的位置切割，但在苹果之间切割也可以有效。

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