Aqua
Đề bài
Mô tả
Aqua là một trò chơi giải đố trên bảng hình chữ nhật gồm hàng và cột. Các hàng được đánh số từ đến từ dưới lên trên, các cột được đánh số từ đến từ trái sang phải. Ô ở hàng thứ , cột thứ được ký hiệu là .
Bảng được chia thành nhiều chuồng liên thông cạnh bởi các đường biên dọc và ngang. Cụ thể, mỗi chuồng là một tập con khác rỗng các ô của bảng, mỗi ô thuộc đúng một chuồng, và các ô của một chuồng tạo thành một vùng liên thông: với hai ô bất kỳ cùng chuồng, luôn có thể đi từ ô này sang ô kia chỉ qua các ô của chuồng đó, mỗi bước đi giữa hai ô chung cạnh.
Ở mỗi chuồng, người ra đề đổ nước từ phía trên xuống. Do trọng lực, nước chảy xuống các ô thấp hơn. Người ra đề đổ nước sao cho thỏa mãn tất cả các điều kiện sau:
- Mỗi ô hoặc đầy nước hoàn toàn, hoặc hoàn toàn trống.
- Một chuồng có thể đầy nước, hoàn toàn trống, hoặc chứa nước một phần.
- Trong mỗi chuồng, tồn tại một mực nước sao cho mọi ô của chuồng nằm dưới mực này đều đầy nước, còn mọi ô nằm trên đều trống. Nói cách khác, nếu và là hai ô cùng chuồng với và ô đầy nước thì ô cũng phải đầy nước. Đặc biệt, hai ô cùng chuồng trên cùng một hàng thì hoặc cùng đầy, hoặc cùng trống.
- Các chuồng được xét độc lập với nhau: quy tắc trên không áp dụng cho các ô thuộc các chuồng khác nhau.
Người ra đề không chỉ tuân theo các quy tắc trên mà còn quan tâm tới số ô đầy nước trên mỗi hàng. Ở một số hàng, anh muốn số ô đầy nước bằng một giá trị cho trước, còn các hàng khác thì không có ràng buộc.
Hãy đếm số cách đổ nước vào các chuồng thỏa mãn tất cả các quy tắc và yêu cầu trên. Hai cách được coi là khác nhau nếu có một ô đầy nước ở cách này nhưng trống ở cách kia.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (). dòng tiếp theo mô tả bảng theo các quy tắc sau:
- Mỗi dòng gồm đúng ký tự, mỗi ký tự là dấu cách, dấu gạch dưới (
_) hoặc dấu gạch đứng (|). - Mọi ký tự ở vị trí chẵn (đánh số từ ) của dòng đầu tiên và dòng cuối cùng đều là dấu gạch dưới, biểu diễn biên trên và biên dưới của bảng.
- Mọi dấu gạch dưới khác biểu diễn một đường biên ngang của chuồng giữa hai ô liên tiếp trên cùng một cột.
- Ký tự đầu tiên và ký tự cuối cùng của mọi dòng (trừ dòng đầu tiên) là dấu gạch đứng, biểu diễn biên trái và biên phải của bảng.
- Mọi dấu gạch đứng khác biểu diễn một đường biên dọc của chuồng giữa hai ô liên tiếp trên cùng một hàng.
Cụ thể, trong dòng sau dòng đầu tiên, dòng thứ mô tả hàng thứ tính từ trên xuống: ký tự ở vị trí (đánh số từ ) là dấu gạch dưới nếu có biên ở ngay dưới ô cột của hàng đó, ký tự ở vị trí là dấu gạch đứng nếu có biên giữa cột và cột của hàng đó. Theo định nghĩa:
- Nếu không có đường biên ngang giữa hai ô liên tiếp trên một cột thì hai ô đó thuộc cùng một chuồng.
- Nếu không có đường biên dọc giữa hai ô liên tiếp trên một hàng thì hai ô đó thuộc cùng một chuồng.
Dòng cuối cùng chứa số nguyên () mô tả yêu cầu về số ô đầy nước trên từng hàng. Nếu , hàng thứ có thể có số ô đầy nước tùy ý. Ngược lại, số ô đầy nước trên hàng này phải đúng bằng .
Dữ liệu đảm bảo bảng có không quá chuồng.
Dữ liệu ra
In ra một số nguyên là số cách đổ nước hợp lệ thỏa mãn các điều kiện, chia lấy dư cho .
Ràng buộc
- Bảng có không quá chuồng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 7 _ | | | _ | | | | | |_| | | | | _| | | | | | | | | | | | || || _| 6 3 7 2 2 2 |
1 | Bảng có chuồng. Cách đổ duy nhất: chuồng chiếm cả cột đầy tới hàng ; chuồng gồm cả cột cùng các ô cột , ở hàng đến (trừ ô ) đầy hoàn toàn; chuồng gồm các ô cột đến ở hàng đến (trừ hai ô , ) đầy hoàn toàn; các chuồng còn lại trống. Số ô đầy trên các hàng lần lượt là . |
| 2 3 _ | | | _| -1 -1 |
3 | Cả bảng là một chuồng: trống, đầy hàng , hoặc đầy cả hai hàng. |
| 3 3 _ | _ | | | | | |||_| -1 1 1 |
1 | Có hai chuồng: chuồng hình chữ U (cột , cột và ô ) và chuồng gồm hai ô , . Hàng có đúng một ô đầy nên chuồng chữ U phải trống và chuồng giữa phải có nước; hàng có đúng một ô đầy nên chuồng giữa đầy. |
Bình luận