Bài tập Code matrix, Search, training Dumv 20/03/2025 0 Comments

placeGarden

Lưu ý: Đây là phiên bản dễ hơn của placeGarden2 (?). Điểm khác biệt ở đây là số truy vấn.

Thầy Karl vừa mới được hay tin rằng ông nội của thầy đã để lại cho thầy một vùng đất trang trại rộng lớn với kích thước n x m. Giờ thầy định xây một vài khu vườn bên trong vùng đất đó, mỗi khu vườn dành cho 1 mục đích riêng (như trồng cây lương thực, cây ăn quả, chăn nuôi trâu, bò, …), để sau này khi thầy về hưu thì còn có việc làm.

Dĩ nhiên, trên vùng đất ấy không thiếu gì vài vật cản (như cây cối, đá tảng, …) Vì vậy, thầy ấy muốn xây mẫu 1 khu vườn với kích thước a x b trước tiên. Là một giáo viên toán tài ba, thầy ấy muốn đếm xem có bao nhiêu cách để xây vườn trên vùng đất ấy.

Cho dãy các chuỗi land chỉ gồm '0' và '1' cho biết đặc điểm vùng đất ấy ('0' tức là có vật cản, '1' tức là chỗ trống, xây được trên đó), các số a và b. Hãy giúp thầy Karl đếm số cách xây vườn kích thước a x b trên vùng đất đã cho.

Ví dụ:

land = ["1011","0111","0110"], a = 2, b = 2 thì placeGarden(land, a, b) = 2

Sau đây là tất cả những cách để xây vườn 2 x 2 trong vùng đất 3 x 4 đã cho:

10**   1011
01**   0**1
0110   0**0

Đầu vào/Đầu ra:

[Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JS.
[Đầu vào] Array of Strings: land
1 ≤ land.length = n ≤ 1000
1 ≤ land[i].length = m ≤ 1000
land[i][j] ∈ {'0', '1'}
[Đầu vào] Integer: a, b
1 ≤ a ≤ n
1 ≤ b ≤ m