Question

1444. Number of Ways of Cutting a Pizza

中文文档

Description

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.

 

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

 

Constraints:

• 1 <= rows, cols <= 50
• rows == pizza.length
• cols == pizza[i].length
• 1 <= k <= 10
• pizza consists of characters 'A' and '.' only.

Solutions

Solution 1

class Solution:
  def ways(self, pizza: List[str], k: int) -> int:
    @cache
    def dfs(i: int, j: int, k: int) -> int:
      if k == 0:
        return int(s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0)
      ans = 0
      for x in range(i + 1, m):
        if s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0:
          ans += dfs(x, j, k - 1)
      for y in range(j + 1, n):
        if s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0:
          ans += dfs(i, y, k - 1)
      return ans % mod

    mod = 10**9 + 7
    m, n = len(pizza), len(pizza[0])
    s = [[0] * (n + 1) for _ in range(m + 1)]
    for i, row in enumerate(pizza, 1):
      for j, c in enumerate(row, 1):
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + int(c == 'A')
    return dfs(0, 0, k - 1)

class Solution {
  private int m;
  private int n;
  private int[][] s;
  private Integer[][][] f;
  private final int mod = (int) 1e9 + 7;

  public int ways(String[] pizza, int k) {
    m = pizza.length;
    n = pizza[0].length();
    s = new int[m + 1][n + 1];
    f = new Integer[m][n][k];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0;
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
      }
    }
    return dfs(0, 0, k - 1);
  }

  private int dfs(int i, int j, int k) {
    if (k == 0) {
      return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
    }
    if (f[i][j][k] != null) {
      return f[i][j][k];
    }
    int ans = 0;
    for (int x = i + 1; x < m; ++x) {
      if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
        ans = (ans + dfs(x, j, k - 1)) % mod;
      }
    }
    for (int y = j + 1; y < n; ++y) {
      if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
        ans = (ans + dfs(i, y, k - 1)) % mod;
      }
    }
    return f[i][j][k] = ans;
  }
}

class Solution {
public:
  int ways(vector<string>& pizza, int k) {
    const int mod = 1e9 + 7;
    int m = pizza.size(), n = pizza[0].size();
    vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(k, -1)));
    vector<vector<int>> s(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
      }
    }
    function<int(int, int, int)> dfs = [&](int i, int j, int k) -> int {
      if (k == 0) {
        return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
      }
      if (f[i][j][k] != -1) {
        return f[i][j][k];
      }
      int ans = 0;
      for (int x = i + 1; x < m; ++x) {
        if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
          ans = (ans + dfs(x, j, k - 1)) % mod;
        }
      }
      for (int y = j + 1; y < n; ++y) {
        if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
          ans = (ans + dfs(i, y, k - 1)) % mod;
        }
      }
      return f[i][j][k] = ans;
    };
    return dfs(0, 0, k - 1);
  }
};

func ways(pizza []string, k int) int {
  const mod = 1e9 + 7
  m, n := len(pizza), len(pizza[0])
  f := make([][][]int, m)
  s := make([][]int, m+1)
  for i := range f {
    f[i] = make([][]int, n)
    for j := range f[i] {
      f[i][j] = make([]int, k)
      for h := range f[i][j] {
        f[i][j][h] = -1
      }
    }
  }
  for i := range s {
    s[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]
      if pizza[i-1][j-1] == 'A' {
        s[i][j]++
      }
    }
  }
  var dfs func(i, j, k int) int
  dfs = func(i, j, k int) int {
    if f[i][j][k] != -1 {
      return f[i][j][k]
    }
    if k == 0 {
      if s[m][n]-s[m][j]-s[i][n]+s[i][j] > 0 {
        return 1
      }
      return 0
    }
    ans := 0
    for x := i + 1; x < m; x++ {
      if s[x][n]-s[x][j]-s[i][n]+s[i][j] > 0 {
        ans = (ans + dfs(x, j, k-1)) % mod
      }
    }
    for y := j + 1; y < n; y++ {
      if s[m][y]-s[m][j]-s[i][y]+s[i][j] > 0 {
        ans = (ans + dfs(i, y, k-1)) % mod
      }
    }
    f[i][j][k] = ans
    return ans
  }
  return dfs(0, 0, k-1)
}

function ways(pizza: string[], k: number): number {
  const mod = 1e9 + 7;
  const m = pizza.length;
  const n = pizza[0].length;
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0).map(() => new Array(k).fill(-1)));
  const s = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      const x = pizza[i - 1][j - 1] === 'A' ? 1 : 0;
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
    }
  }
  const dfs = (i: number, j: number, k: number): number => {
    if (f[i][j][k] !== -1) {
      return f[i][j][k];
    }
    if (k === 0) {
      return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
    }
    let ans = 0;
    for (let x = i + 1; x < m; ++x) {
      if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
        ans = (ans + dfs(x, j, k - 1)) % mod;
      }
    }
    for (let y = j + 1; y < n; ++y) {
      if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
        ans = (ans + dfs(i, y, k - 1)) % mod;
      }
    }
    return (f[i][j][k] = ans);
  };
  return dfs(0, 0, k - 1);
}