Domino trên lưới
Cho một lưới gồm hàng và cột. Mỗi ô của lưới hoặc trống (ký hiệu là ký tự .) hoặc bị cấm (ký hiệu là ký tự #). Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải.
Một quân domino chiếm đúng hai ô kề nhau, hoặc nằm trong cùng một hàng (kề nhau theo chiều ngang) hoặc nằm trong cùng một cột (kề nhau theo chiều dọc). Một quân domino chỉ có thể được đặt nếu cả hai ô mà nó chiếm đều trống và đều nằm trong lưới.
Cho truy vấn. Mỗi truy vấn gồm bốn số nguyên mô tả một hình chữ nhật con với ô trái-trên là và ô phải-dưới là . Với mỗi truy vấn, hãy đếm số cách đặt một quân domino sao cho cả hai ô mà nó chiếm đều nằm hoàn toàn bên trong hình chữ nhật con này.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- dòng tiếp theo, mỗi dòng chứa một xâu độ dài gồm các ký tự
.và#mô tả lưới. - Dòng tiếp theo chứa một số nguyên — số truy vấn.
- Mỗi dòng trong dòng tiếp theo chứa bốn số nguyên mô tả truy vấn thứ .
Dữ liệu ra
In ra dòng, dòng thứ là số cách đặt một quân domino trong hình chữ nhật con của truy vấn thứ .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 8 ....#..# .#...... ##.#.... ##..#.## ........ 4 1 1 2 3 4 1 4 1 1 2 4 5 2 5 5 8 |
4 0 10 15 |
Truy vấn 1: hình chữ nhật ở góc trên-trái có cách đặt domino. Truy vấn 2: hình chữ nhật không thể chứa domino nào. |
| 1 1 . 1 1 1 1 1 |
0 | Một ô đơn lẻ không thể chứa quân domino nào (domino cần hai ô). |
Bình luận