P14687 [ICPC 2025 Yokohama R] U-Shaped Panels

你家后院有一个长方形的池塘。由于池塘的长和宽都是 $1$ 米的整数倍，因此可以将池塘看作由 $1$ 米见方的方格组成。 你总觉得池塘太大了，想用存放在谷仓里的面板覆盖池塘的一部分方格。这些面板尺寸和形状都相同，由排列成 U 形的 $1$ 米见方的木板组成。面板的整体尺寸为 $k$ 米 × $k$ 米，该正方形的三条边上共有 $3k - 2$ 块木板。其余部分，即 $(k - 2) \times (k - 1)$ 的长方形区域，是空的。图 H.1 展示了一个尺寸为 $k = 5$ 的面板。 :::align{center}  图 H.1. 尺寸为 $k = 5$ 的面板（左）及其俯视图（右） ::: 你计划用这些面板覆盖池塘的某些 $1$ 米见方的方格，其余部分则不覆盖。面板的放置必须使每块木板恰好覆盖一个方格。只要满足这一点，面板的方向可以任意选择。面板之间不能相互重叠，也不能超出池塘范围。 判断你的计划是否可行。

输入包含一个或多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个用例的格式如下。 $$ n\ m\ k $$ $$ s_1 $$ $$ \vdots $$ $$ s_n $$ 第一行包含三个整数 $n$、$m$ 和 $k$。整数 $n$ 和 $m$ 分别表示池塘的长度和宽度 ($5 \le n \le 1000$, $5 \le m \le 1000$)。整数 $k$ 表示 U 形面板的尺寸 ($5 \le k \le 1000$)。接下来的 $n$ 行表示你的计划。其中第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$，由字符 '#' 和 '.' 组成。假设一个 $1$ 米见方的方格位于 $(r, c)$，如果它距离前边 $r-1$ 米到 $r$ 米，距离左边 $c-1$ 米到 $c$ 米。对于每个 $i$ 和 $j$，如果 $s_i$ 的第 $j$ 个字符是 '#'，则位于 $(i, j)$ 的方格应被一块面板木板完全覆盖。否则，该方格应保持完全不被覆盖。 所有测试用例的 $n$ 之和不超过 $1000$。$m$ 也满足相同条件。

对于每个测试用例，如果你的计划可行，则输出一行 yes；否则输出 no。

翻译由 DeepSeek V3 完成