解题思路

核心思路

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

关键约束：

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

P4809.第2题-矩阵印章染色

1000ms

Tried: 83

Accepted: 25

Difficulty: 4

所属公司 : 字节

算法与标签>模拟

题目内容

小红拿到了一个矩阵， $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

输入

预期输出（选填）

解题思路

核心思路

P4809.第2题-矩阵印章染色

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About