P13314 [GCJ 2012 Qualification] Hall of Mirrors

你生活在一个二维平面上，你最喜欢去的地方之一是镜厅。镜厅是一个房间（当然是二维的），以网格的形式铺设。网格上的每个格子要么放置着一个方形镜子，要么是空地，要么是你自己。你自身的宽度和高度都为 $0$，且你位于你所在格子的正中心。 尽管你很小，但只要反射光线**正好**返回到你这里，你就能看到自己的倒影。例如，考虑如下布局，其中 `#` 表示完全填满格子的方形镜子，`.` 表示空地，大写字母 `X` 表示你处于该格子的中心： ``` ###### #..X.# #.#..# #...## ###### ``` 如果你直视正上方或正右方，你都能看到自己的倒影。 不幸的是，镜厅里雾很大，所以你看不超过 $D$ 单位的距离。假设 $D=3$。如果你向上看，你的倒影距离你 1 单位远（0.5 到镜子，0.5 再回来）。如果你向右看，你的倒影距离你 3 单位远（1.5 到镜子，1.5 再回来），你能看到它。如果你向下看，你的倒影距离你 5 单位远，你就看不到了。 理解光线在镜厅中的传播方式非常重要。光线会沿直线传播，直到遇到镜子。如果光线击中了镜子的某一部分（不是角落），它会以正常方式反射：反射角等于入射角。如果光线正好打在镜子的角上，情况会更复杂。下图解释了各种情况： 在下面这些情况下，光线到达了一个角落，并被反射，方向发生了变化：  前两种情况中，光线以与长镜中点相同的方式，被两块相邻镜子交汇处反射。第三种情况中，光线到达了三块相邻镜子的角落，正好沿原路返回。 在下面这些情况下，光线到达了一个或多个镜子的角落，但不会反弹，而是继续保持原方向前进：  这种情况发生在光线到达镜子角落的距离为 $0$，但要继续保持原方向前进时并不需要穿过镜子。这样，光线就可以穿过对角相邻的两块镜子之间的“零宽度”空隙——好在光线自身也没有宽度，所以它能穿过去！ 在最后一种情况下，光线到达了一块镜子的角落并被“消灭”：  此时镜子正好挡在光路上，且光线没有同时到达其他镜子的角落。 注意：光线遇到你时会停止，但必须正好击中你所在格子的中心。 你能看到多少个自己的倒影？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个用空格分隔的整数 $H$、$W$ 和 $D$。接下来 $H$ 行，每行 $W$ 个字符，表示该组测试的镜厅地图，含义如上所述。

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为你能看到的自己倒影的数量。

**样例说明** 在第 1 个样例中，如果你直视正上、下、左、右，光线恰好传播距离为 1。 在第 2 个样例中，如果你沿对角线（右上、左上、右下、左下）方向看，光线传播距离为 $1.414\dots$。由于光线不会穿过你自己，直视正上方只能看到一个自己的倒影。 在第 5 个样例中，虽然附近的镜子足够近可以反射光线回来，但如果光线正好打在镜子的角落，它会被消灭而不是反射。 **限制条件** - $1 \leq T \leq 100$ - $3 \leq H, W \leq 30$ - $1 \leq D \leq 50$ - 每个地图中的字符均为 `#`、`.` 或 `x` - 每个地图中恰好有一个 `x` - 每个地图的第一行、最后一行、第一列和最后一列全部为 `#` **测试集 1（15 分，可见结果）** - `#` 的总数不超过 $2W + 2H - 4$ **测试集 2（25 分，隐藏结果）** - 小数据集的限制不适用 翻译由 ChatGPT-4.1 完成。