CSES - Maximum Building II | Tòa Nhà Lớn Nhất II

Xem PDF
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một bản đồ của một khu rừng nơi có một số ô vuông trống và một số ô vuông có cây.

Bạn muốn đặt một tòa nhà hình chữ nhật trong rừng mà không có cây nào cần bị chặt. Đối với mỗi kích thước tòa nhà, nhiệm vụ của bạn là tính toán số cách bạn có thể làm điều này.

Input

Dòng đầu vào đầu tiên chứa các số nguyên \(n\) và \(m\): kích thước của khu rừng.

Sau đó, khu rừng được mô tả. Mỗi ô vuông trống (.) hoặc có cây (*).

Output

In \(n\) dòng, mỗi dòng chứa \(m\) số nguyên.

Constraints

  • \(1 \leq n, m \leq 1000\)

Example

Input:

4 7  
...*.*.  
.*.....  
.......  
......*

Output:

24 17 13 9 6 3 1  
16 9 7 5 3 1 0  
9 3 2 1 0 0 0  
3 0 0 0 0 0 0

Explanation: Ví dụ, có \(5\) vị trí có thể cho một tòa nhà có kích thước \(2 \times 4\).

Bình luận


  • 0
    vanphukhang_0604    2:00 p.m. 16 Tháng 8, 2023 ← chỉnh sửa 4

    CSES - Maximum Building II | Tòa nhà lớn nhất II

    Bạn được cho một bản đồ của một khu rừng nơi có một số ô vuông trống và một số ô vuông có cây.

    Bạn muốn đặt một tòa nhà hình chữ nhật trong rừng mà không phải chặt cây nào. Đối với mỗi kích thước tòa nhà, nhiệm vụ của bạn là tính toán số cách bạn có thể làm điều này.

    Input

    • Dòng đầu chứa hai số nguyên \(n\) và \(m \ (1 \leq n, m \leq 1000)\): kích thước của khu rừng.
    • Những dòng tiếp theo mô tả khu rừng. Ô trống được biểu diễn bằng kí tự ., ô có cây được biểu diễn bằng kí tự *.

    Output

    • In ra \(n\) dòng, mỗi dòng chứa \(m\) số nguyên.

    Example

    Test 1

    Input 
    4 7  
...*.*.
.*.....
.......
......*
    Output 
    24 17 13 9 6 3 1
16 9 7 5 3 1 0
9 3 2 1 0 0 0
3 0 0 0 0 0 0
    Note

    Giải thích: Ví dụ, có \(5\) vị trí có thể đặt một toà nhà có kích thước \(2 \times 4\).