解题思路

核心思路

题目要求判断一个给定矩阵，是否可以由若干个 互不相邻（包括边和角） 的 $2 \times 2$ 红色块（即 *）构成。

关键约束：

1. 每个红色块必须是完整的 $2 \times 2$。

题目内容

小红拿到了一个矩阵，$n$ 行 $m$ 列共 $n \times m$ 个小方格。小红有一个 $2 \times 2$ 的印章，每次可以将一个$2 \times 2$的子矩阵染成红色，每个格子只能被染一次。小红染了若干个红色的 $2 \times 2$ 块，并且最终保证了每个 $2 \times 2$ 红色块都是不相邻的（如果两个红色块共用了同一个边或者同一个角，则称为两个红色块相邻）。

例如：下面矩阵为非法的，因为两个 $2 \times 2$ 红色块相邻了(共用了同一个角):

$**..$

$**..$

$..**$

$..**$

小红忘了自己的染色过程，她拿到了一个矩阵，她想知道这个矩阵是否是按她的要求染色的？

共有 $t$ 组询问。

输入描述

第一行输入一个正整数 $t$，代表询问的次数。

对于每组询问，先输入两个正整数 $n$ 和 $m$，代表矩阵的行数和列数。

接下来的 $n$ 行，每行输入一个长度为 $m$ 的字符串。字符*代表格子被染成红色，.代表未被染色。

$1 \le t, n, m \le 50$

输出描述

输出 $t$ 行，每行对应一组询问的答案。

若该图形是小红染色的，则输出 "$Yes$"。否则输出"$No$"。

样例1

输入

3
4 4
**..
**..
..**
..**
4 5
**...
**...
...**
...**
2 2
*.
..

输出

No
Yes
No