Bạn sống trong một mặt phẳng 2 chiều, và một trong những địa điểm yêu thích của bạn là Phòng Gương (Hall of Mirrors). Phòng Gương là một căn phòng (tất nhiên là 2 chiều) được bố trí trên một lưới ô vuông. Mỗi ô vuông trên lưới chứa một tấm gương hình vuông, không gian trống, hoặc chính bạn. Bạn có chiều rộng bằng 0 và chiều cao bằng 0, và bạn nằm ở chính giữa ô lưới của mình.

Mặc dù rất nhỏ, bạn vẫn có thể nhìn thấy hình ảnh phản chiếu của mình khi nó được phản chiếu chính xác trở lại vị trí của bạn. Ví dụ, hãy xem xét cách bố trí sau, trong đó '#' biểu thị một gương vuông lấp đầy ô của nó, '.' biểu thị không gian trống và chữ cái in hoa 'X' biểu thị bạn đang ở trung tâm của ô đó:

######
#..X.#
#.#..#
#...##
######

Nếu bạn nhìn thẳng lên trên hoặc thẳng sang bên phải, bạn sẽ có thể nhìn thấy hình ảnh phản chiếu của mình.

Thật không may, trong Phòng Gương rất nhiều sương mù, vì vậy bạn không thể nhìn xa hơn \(D\) đơn vị. Giả sử \(D=3\). Nếu bạn nhìn lên trên, hình ảnh phản chiếu của bạn sẽ cách 1 đơn vị (0.5 đến gương và 0.5 quay lại). Nếu bạn nhìn sang phải, hình ảnh phản chiếu của bạn sẽ cách 3 đơn vị (1.5 đến gương và 1.5 quay lại), và bạn sẽ có thể nhìn thấy nó. Nếu bạn nhìn xuống dưới, hình ảnh phản chiếu của bạn sẽ cách 5 đơn vị và bạn sẽ không thể nhìn thấy nó.

Điều quan trọng là phải hiểu cách ánh sáng truyền đi trong Phòng Gương. Ánh sáng truyền theo đường thẳng cho đến khi chạm vào gương. Nếu ánh sáng chạm vào bất kỳ phần nào của gương ngoại trừ góc của nó, nó sẽ được phản xạ theo cách thông thường: nó sẽ bật ra với góc phản xạ bằng góc tới. Mặt khác, nếu ánh sáng chạm vào góc của một tấm gương, tình hình sẽ phức tạp hơn. Các sơ đồ sau đây giải thích các trường hợp:

Trong các trường hợp sau, ánh sáng tiếp cận một góc và được phản xạ, làm thay đổi hướng của nó:

Trong hai trường hợp đầu tiên, ánh sáng tiếp cận hai gương liền kề tại điểm chúng gặp nhau. Ánh sáng được phản xạ theo cùng một cách như thể nó đã chạm vào giữa một tấm gương dài. Trong trường hợp thứ ba, ánh sáng tiếp cận các góc của ba gương liền kề và quay trở lại chính xác hướng mà nó đã đến.

Trong các trường hợp sau, ánh sáng tiếp cận các góc của một hoặc nhiều gương, nhưng không bật lại mà tiếp tục đi theo hướng cũ:

Điều này xảy ra khi ánh sáng đạt đến khoảng cách 0 từ góc của một tấm gương, nhưng sẽ không phải đi qua gương để tiếp tục đi theo cùng một hướng. Theo cách này, một tia sáng có thể đi qua giữa hai gương nằm chéo nhau -- thực tế là đi qua một khoảng không gian có kích thước 0. Thật may là tia sáng cũng có kích thước 0, nên nó vừa khít!

Trong trường hợp cuối cùng, ánh sáng tiếp cận góc của một tấm gương và bị triệt tiêu:

Lưu ý rằng ánh sáng dừng lại khi nó chạm vào bạn, nhưng nó phải chạm vào đúng tâm ô lưới của bạn.

Bạn có thể nhìn thấy bao nhiêu hình ảnh của chính mình?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách, \(H\), \(W\) và \(D\). \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) ký tự. Các ký tự tạo thành bản đồ của Phòng Gương cho bộ test đó, như mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng hình ảnh phản chiếu của chính bạn mà bạn có thể nhìn thấy.

Ràng buộc

• \(1 \le T \le 100\).
• \(3 \le H, W \le 30\).
• \(1 \le D \le 50\).
• Tất cả các ký tự trong mỗi bản đồ sẽ là '#', '.', hoặc 'X'.
• Chính xác một ký tự trong mỗi bản đồ sẽ là 'X'.
• Hàng đầu tiên, hàng cuối cùng, cột đầu tiên và cột cuối cùng của mỗi bản đồ sẽ hoàn toàn chứa các ký tự '#'.

Phân nhóm

• Test set 1 (Visible): Sẽ không có quá \(2W+2H-4\) ký tự '#'.
• Test set 2 (Hidden): Hạn chế từ Small dataset không áp dụng.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

6
3 3 1
###
#X#
###
3 3 2
###
#X#
###
4 3 8
###
#X#
#.#
###
7 7 4
#######
#.....#
#.....#
#..X..#
#....##
#.....#
#######
5 6 3
######
#..X.#
#.#..#
#...##
######
5 6 10
######
#..X.#
#.#..#
#...##
######

Case #1: 4
Case #2: 8
Case #3: 68
Case #4: 0
Case #5: 2
Case #6: 28

Nguồn

Google Code Jam 2012, Vòng loại, bài Hall of Mirrors.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.