Try   HackMD

1444.Number of Ways of Cutting a Pizza

tags: Hard,Array,Matrix,DP

1444. 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 109 + 7.

範例

Example 1:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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.

解答

Python

class Solution: def ways(self, pizza: List[str], k: int) -> int: rows, cols = len(pizza), len(pizza[0]) @cache def has_apple(up, left, bottom, right): return any(any(pizza[r][c] == 'A' for c in range(left, right)) for r in range(up, bottom)) @cache def dp(up, left, k): if k == 1: if has_apple(up, left, rows, cols): return 1 count = 0 for r in range(up, rows): if has_apple(up, left, r+1, cols): count += dp(r+1, left, k-1) for c in range(left, cols): if has_apple(up, left, rows, c+1): count += dp(up, c+1, k-1) return count return dp(0, 0, k) % (10 ** 9 + 7)

Yen-Chi ChenFri, Mar 31, 2023

Reference

回到題目列表