← 返回题目列表

Codeforces · 1059/B

B. 伪造

中文机器翻译题面 查看原题

学生安德烈整个学期都在逃体育课,现在他必须以某种方式在这门科目上获得及格分数。显然,通过法律手段不可能做到这一点,但安德烈并没有放弃。他从当地一家医院拿到了一张空证明,准备利用自己对当地医生字迹的了解,制作一份伪造的病假证明。然而,写完大部分证明后,安德烈突然发现医生的签名是不可能伪造的。或者是吗?

为简单起见,签名表示为 $$$n\times m$$$ 网格,其中每个单元格要么充满墨水,要么为空。如果 Andrey 的笔完全包含在网格内,则可以填充 $$$3\times3$$$ 正方形,而无需其中心单元,如下所示。

xxxx.xxxx

确定是否可以在空的 $$$n\times m$$$ 网格上伪造签名。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n, m \le 1000$$$)。

接下来是 $$$n$$$ 行,每行包含 $$$m$$$ 个字符。每个字符要么是“.”(代表空单元格),要么是“#”(代表墨水填充单元格)。

输出

如果Andrey可以伪造签名,则输出“YES”。否则输出“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

3 3
###
#.#
###

输出 #1

YES

输入 #2

3 3
###
###
###

输出 #2

NO

输入 #3

4 3
###
###
###
###

输出 #3

YES

输入#4

5 7
.......
.#####.
.#.#.#.
.#####.
.......

输出#4

YES

注意

在第一个示例中,Andrey 可以绘制以 $$$(2, 2)$$$ 为中心的正方形边框。

在第二个样本中,签名不可能伪造。

在第三个示例中,Andrey 可以绘制以 $$$(2, 2)$$$ 和 $$$(3, 2)$$$ 为中心的正方形边框:

1. 我们有一份明确的文件:…………
2. 使用中心位于 $$$(2, 2)$$$ 的笔。 ####.####...
3. 使用中心位于 $$$(3, 2)$$$ 的笔。 ############

在第四个示例中,Andrey 可以绘制以 $$$(3, 3)$$$ 和 $$$(3, 5)$$$ 为中心的正方形的边界。