trang chủ / đề bài / icpc19_reg_h

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 r hàng và c cột. Trên mỗi hàng và mỗi cột có một gợi ý là một dãy số a1,a2,…,ak, 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 a1 ô đ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 a2 ô đ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 ak ô đ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 a 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ó 7 ô với gợi ý a=1,2 (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 2 chứ không phải 1).
  • Hàng ....### không hợp lệ (chỉ có một khối đen, dài 3).

Cho r, c 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 r và c (1≤r,c≤6).

r dòng tiếp theo, dòng thứ i chứa gợi ý của hàng thứ i: một số nguyên không âm k, tiếp theo là k số nguyên dương a1,a2,…,ak thỏa mãn ∑i=1kai+k−1≤c.

c dòng tiếp theo, dòng thứ i chứa gợi ý của cột thứ i: một số nguyên không âm k, tiếp theo là k số nguyên dương a1,a2,…,ak thỏa mãn ∑i=1kai+k−1≤r.

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

  • 1≤r,c≤6
  • Gợi ý của mỗi hàng thỏa mãn ∑ai+k−1≤c, gợi ý của mỗi cột thỏa mãn ∑ai+k−1≤r.

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à a=1 (đúng một ô đen), nhưng gợi ý ba cột nói rằng ô ở cột 1 đen, ô ở cột 2 trắng và ô ở cột 3 đen, tức là hai ô đen. Không có cách tô nào.

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