trang chủ / đề bài / icpc22_reg_a

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 r hàng và c cột. Các hàng được đánh số từ 1 đến r từ dưới lên trên, các cột được đánh số từ 1 đến c từ trái sang phải. Ô ở hàng thứ i, cột thứ j được ký hiệu là (i,j).

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 (r1,c1) và (r2,c2) là hai ô cùng chuồng với r1≤r2 và ô (r2,c2) đầy nước thì ô (r1,c1) 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 r và c (1≤r,c≤20). r+1 dòng tiếp theo mô tả bảng theo các quy tắc sau:

  • Mỗi dòng gồm đúng 2·c+1 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ừ 1) 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 r dòng sau dòng đầu tiên, dòng thứ k mô tả hàng thứ k tính từ trên xuống: ký tự ở vị trí 2j (đánh số từ 1) là dấu gạch dưới nếu có biên ở ngay dưới ô cột j của hàng đó, ký tự ở vị trí 2j+1 là dấu gạch đứng nếu có biên giữa cột j và cột j+1 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 r số nguyên x1,x2,…,xr (−1≤xi≤c) mô tả yêu cầu về số ô đầy nước trên từng hàng. Nếu xi=−1, hàng thứ r−i+1 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 xi.

Dữ liệu đảm bảo bảng có không quá 20 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 109+7.

Ràng buộc

  • 1≤r,c≤20
  • −1≤xi≤c
  • Bảng có không quá 20 chuồng.

Ví dụ

Input Output Giải thích
6 7
       _ 
| |   |  _  |
| | | | |_| |
| |  |   _|
| |   | |   |
| | | | |   |
||  || _|
6 3 7 2 2 2
1 Bảng 6×7 có 8 chuồng. Cách đổ duy nhất: chuồng chiếm cả cột 1 đầy tới hàng 4; chuồng gồm cả cột 5 cùng các ô cột 6, 7 ở hàng 4 đến 6 (trừ ô (5,6)) đầy hoàn toàn; chuồng gồm các ô cột 2 đến 4 ở hàng 4 đến 6 (trừ hai ô (5,3), (5,4)) đầy hoàn toàn; các chuồng còn lại trống. Số ô đầy trên các hàng 6,5,…,1 lần lượt là 6,3,7,2,2,2.
2 3
   _ 
|     |
|  _|
-1 -1
3 Cả bảng là một chuồng: trống, đầy hàng 1, 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 1, cột 3 và ô (3,2)) và chuồng gồm hai ô (1,2), (2,2). Hàng 1 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 2 có đúng một ô đầy nên chuồng giữa đầy.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0