Lát gạch Domino trên lưới khuyết

Buổi 33 — Bitmask DP & SOS DP
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved