trang chủ / đề bài / icpc20_reg_h

Tô màu lục giác

Đề bài

Mô tả

Cho một lưới lục giác gồm n hàng, trong đó n là số lẻ. Các hàng được đánh số từ 1 đến n từ trên xuống dưới. Hàng lẻ có đúng n ô lục giác, hàng chẵn có đúng n−1 ô lục giác. Ký hiệu ô lục giác thứ j (tính từ trái sang) của hàng i là (i,j).

Các ô lục giác có một đỉnh hướng lên trên. Hai ô liên tiếp trong cùng một hàng có chung một cạnh thẳng đứng. Mỗi hàng chẵn lệch sang phải nửa ô so với hàng lẻ, nên ô (i,j) của hàng chẵn nằm khít giữa các ô (i−1,j), (i−1,j+1) ở hàng trên và (i+1,j), (i+1,j+1) ở hàng dưới, đồng thời có chung một cạnh với mỗi ô trong bốn ô đó. Toàn bộ lưới là một hình liền, không có lỗ. Ví dụ, với n=3 lưới có 3+2+3=8 ô.

Mỗi ô (i,j) được gán một số nguyên ai,j trong khoảng từ −1 đến 6.

Ta tô màu một số cạnh của các ô lục giác (mỗi cạnh chung của hai ô chỉ được tính là một cạnh). Một cách tô là hợp lệ nếu thỏa mãn cả hai điều kiện sau:

  1. Với mọi ô (i,j), hoặc ai,j=−1, hoặc ai,j bằng số cạnh được tô của ô (i,j).
  2. Các cạnh được tô tạo thành một hoặc nhiều vòng khép kín. Mỗi vòng không được tự cắt, và hai vòng khác nhau không được có chung đỉnh hay cạnh nào.

Hỏi có bao nhiêu cách tô hợp lệ?

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên lẻ n.
  • n dòng tiếp theo chứa các số ai,j. Dòng thứ i chứa đúng n số nếu i lẻ và n−1 số nếu i chẵn.

Dữ liệu ra

In ra một số nguyên: số cách tô hợp lệ.

Ràng buộc

  • 1≤n≤7, n lẻ.
  • −1≤ai,j≤6.

Ví dụ

Input Output Giải thích
3
-1 2 -1
2 2
1 -1 1
1 Chỉ có đúng một cách tô thỏa mãn mọi ràng buộc.
7
-1 4 5 1 0 -1 -1
-1 3 2 0 0 1
-1 4 -1 1 0 -1 -1
1 3 4 2 2 4
0 2 3 -1 4 4 2
-1 4 4 3 3 2
1 -1 -1 -1 4 2 -1
1 Chỉ có đúng một cách tô hợp lệ.
3
-1 2 -1
2 2
-1 -1 -1
4 Giống ví dụ thứ nhất nhưng hàng cuối không còn ràng buộc, nên có 4 cách tô hợp lệ.

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