VMTILE - Lát gạch 5
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một sàn nhà kích thước M*N , được chia thành các hình vuông nhỏ kích thước 1*1. Trên đó có một số ô cấm.
Người ta cần lát kín sàn bằng các viên gạch 1*2 và 2*1, sao cho:
- Không có 2 viên gạch nào chồng lên nhau
- Không có viên gạch nào lát đè lên ô cấm
- Ngoài các ô cấm, tất cả các ô còn lại đều được lát bởi đúng 1 viên gạch
Nhiệm vụ: Bạn được download input là thông tin về 10 sàn nhà. hãy tính số cách lát sàn thỏa mãn các điều kiện trên, và submit 1 file text gồm 10 dòng, mỗi dòng chứa một số nguyên dương duy nhất, là số cách lát sàn nhà thỏa mãn, lấy modulo 10 9 + 7.
Input
Dòng đầu chứa số nguyên dương T (1 ≤ T ≤ 10).
Tiếp theo là T test, mỗi test gồm:
- Dòng đầu chứa 2 số nguyên dương M, N (1 ≤ M, N ≤ 1000).
- Tiếp theo là M dòng, mỗi dòng gồm đúng N ký tự. Ký tự ở hàng i, cột j là '#' nếu ô tương ứng là ô cấm, và '.' trong trường hợp ngược lại.
Bộ test có thể download ở: link
Output
Gồm T dòng, mỗi dòng chứa một số nguyên dương duy nhất là số cách lát sàn M*N mod 10 9 + 7.
Chấm điểm
Trong quá trình thi, chương trình của bạn sẽ được chấm với 5 test đầu tiên . Trong quá trình thi, điểm mà bạn nhận được thể hiện phần trăm test mà bạn giải đúng trong số 5 test này (trên thang điểm 100 ).
Example
Input: 4 5 4 .... .#.. .... .... .... 5 4 .... .... .... .... .... 5 4 ...# .... .... .... #... 5 5 ##### ..... ..... ##### ##### Output: 0 95 23 8
- Người up: voj