Lát gạch sàn thông minh
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một sàn nhà hình chữ nhật kích thước $N \times M$ gồm $N$ hàng và $M$ cột. Mỗi ô trên sàn có thể là ô trống (.) hoặc ô bị hỏng (#).
Ta cần lát kín tất cả các ô trống bằng các viên gạch domino kích thước $1 \times 2$ hoặc $2 \times 1$ sao cho các viên gạch không chồng lên nhau, không chờm ra ngoài bảng và không đặt lên ô #. Hãy đếm số cách lát hợp lệ, lấy phần dư cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10$, $1 \le M \le 100$).
- $N$ dòng tiếp theo, mỗi dòng là một xâu độ dài $M$ chỉ gồm các ký tự
.và#.
Kết quả
- In ra một số nguyên duy nhất là số cách lát hợp lệ modulo $10^9 + 7$.
Subtasks
- Subtask 1 (25% số điểm): $N \le 4$, $M \le 10$.
- Subtask 2 (25% số điểm): Không có ô
#. - Subtask 3 (50% số điểm): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 3 3 ... .#. ... |
2 |
Community Discussion