Lát gạch Domino trên lưới khuyết
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một lưới ô vuông kích thước $N \times M$, trong đó một số ô bị hỏng (ký hiệu #) và không thể lát gạch, các ô còn lại là ô trống (ký hiệu .). Hãy đếm số cách lát các viên gạch Domino kích thước $1 \times 2$ (có thể đặt ngang hoặc dọc) để phủ kín toàn bộ các ô trống, không đè lên nhau và không đè lên ô hỏng. In ra kết quả chia dư cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 8$, $1 \le M \le 50$).
- $N$ dòng tiếp theo, mỗi dòng là một xâu độ dài $M$ gồm các ký tự
.và#.
Dữ liệu ra
- In ra số cách lát thỏa mãn chia dư cho $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 2 3 ... ... |
3 |
| 2 2 .# .. |
0 |
Giới hạn
- $1 \le N \le 8$
- $1 \le M \le 50$
Community Discussion