Hanjie
Đề bài
Mô tả
Hanjie, còn được gọi là Nonogram hay Picross, là các câu đố logic bằng hình ảnh: mỗi ô của một bảng phải được tô màu đen hoặc trắng theo các con số ghi ở cạnh bảng.
Cụ thể, cho một bảng gồm hàng và cột. Trên mỗi hàng và mỗi cột có một gợi ý là một dãy số , nghĩa là: nếu đi qua các ô của hàng đó từ trái sang phải (hoặc của cột đó từ trên xuống dưới), ta sẽ gặp lần lượt:
- không hoặc nhiều ô trắng liên tiếp,
- tiếp theo là đúng ô đen liên tiếp,
- tiếp theo là ít nhất một ô trắng liên tiếp,
- tiếp theo là đúng ô đen liên tiếp,
- tiếp theo là ít nhất một ô trắng liên tiếp,
- ...
- tiếp theo là đúng ô đen liên tiếp,
- tiếp theo là không hoặc nhiều ô trắng liên tiếp.
Lưu ý dãy có thể rỗng; khi đó mọi ô của hàng (hoặc cột) đó đều phải màu trắng.
Ví dụ, xét một hàng có ô với gợi ý (ký hiệu # là ô đen, . là ô trắng):
- Hàng
.#...##là hợp lệ. - Hàng
##...##không hợp lệ (khối đen đầu tiên dài chứ không phải ). - Hàng
....###không hợp lệ (chỉ có một khối đen, dài ).
Cho , và gợi ý của mọi hàng và mọi cột, hãy đếm số cách tô màu khác nhau thỏa mãn tất cả các gợi ý. Hai cách tô được coi là khác nhau nếu có ít nhất một ô có màu khác nhau.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và ().
dòng tiếp theo, dòng thứ chứa gợi ý của hàng thứ : một số nguyên không âm , tiếp theo là số nguyên dương thỏa mãn .
dòng tiếp theo, dòng thứ chứa gợi ý của cột thứ : một số nguyên không âm , tiếp theo là số nguyên dương thỏa mãn .
Dữ liệu ra
In ra một số nguyên là số cách tô màu khác nhau thỏa mãn mọi gợi ý.
Ràng buộc
- Gợi ý của mỗi hàng thỏa mãn , gợi ý của mỗi cột thỏa mãn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 1 1 1 1 1 1 1 |
2 | Mỗi hàng và mỗi cột có đúng một ô đen. Có hai cách: tô hai ô trên đường chéo chính, hoặc hai ô trên đường chéo phụ. |
| 1 3 1 1 1 1 0 1 1 |
0 | Ví dụ bổ sung (không có trong đề gốc). Gợi ý của hàng là (đúng một ô đen), nhưng gợi ý ba cột nói rằng ô ở cột đen, ô ở cột trắng và ô ở cột đen, tức là hai ô đen. Không có cách tô nào. |
Bình luận